Lecture No. 21
Dated: 02-01-2025
Mealy Machine
It consists of the following
- A finite
set1 ofstates\(q_0, q_1, q_2, \ldots, q_n\) where \(q_0\) is theinitial state. - An
alphabet2 of letters \(\Sigma = \{a, b, c, \ldots\}\) from which the inputstrings2 are formed. - An
alphabet2 of letters \(\Gamma = \{x, y, z, \ldots\}\) from which the outputstrings2 are formed. - A pictorial representation with
statesand directed edges labeled by an input letter along with an output character, showing how to go from onestateto another.
Example
\[\text{states} = q_0, q_1, q_2, q_3\]
\[\Sigma = \{a, b\}\]
\[\Gamma = \{0, 1\}\]
| Input | a | b | b | a | b | b | b | a | |
|---|---|---|---|---|---|---|---|---|---|
| States | \(q_0\) | \(q_1\) | \(q_2\) | \(q_3\) | \(q_3\) | \(q_0\) | \(q_3\) | \(q_0\) | \(q_1\) |
| Output | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
Complementing Machine
Constructing the Incrementing Machine
If the letter is \(0\) at initial state then we change it to \(1\) and enter no change state.
Otherwise if we read a \(1\) then we change it to \(0\) and enter a state where as we keep reading \(1\), we remain in that carry state and change the \(1\) to \(0\) but if we read a \(0\) afterwards, we change it to \(1\) and enter the no carry state.