88
Theory of Computer Science
Construction
(i) We have to define the output function;: for the Mealy machine as
a function of the present state and the input symbol. We define;: by
X('1, a) = }eCoCq, a»
for all states '1 and input symbols a.
(ii) The transition function IS the :..;ame as that of the gIven Moore
machine.
EXAMPLE 3.l0
Construct a Mealy Machine which is equivalent to the Moore machine given
by Table 3.14.
TABLE 3.14 Moore Machine of Example 3.10
Present state
-;qo
q,
q2
q3
Solution
a = 0
Next state
a = 1
Output
o
1
o
o
We must follow the reverse procedure of converting a Mealy machine into a
Moore machine. In the case of the Moore machine, for every input symbol we
form the pair consisting of the next state and the corresponding output and
reconstruct the table for the Mealy Machine. For example, the states CJ3 and ' 11
in the next state column should be associated with outputs 0 and I, respectively.
The transition table for the Mealy machine is given by Table 3.15.
TABLE 3.15 Mealy Machine of Example 3.10
Present state
Next state
a = 0
a =
state
output
state
output
-;qc
q3
0
q,
1
q
q,
1
q2
0
q2
q2
0
q3
0
q3
q3
0
qo
0
Note: We can reduce the number of states in any model by considering states
with identical transitions. If two states have identical transitions (i.e. the rows
cOlTesponding to these two states are identical), then we can delete one of them.
EXAMPLE 3.11
Consider the Moore machine desclibed by the transition table given by
Table 3.16. Construct the corresponding Mealy rnachine.