Chapter 3: The Theory of Automata g 87
TABLE 3.12 Revised State Table for Example 3.9
Present state
a = 0
Next state
a = 1
Output
--+q.,
q3
G2C
1
q20
q"
q40
0
q2',
q,
Q4C
1
q3
q21
q,
0
Q4CJ
q41
q3
~
q41
q4'
q3
1
Table 3.12 gives the Moore machine. Here we observe that the initial state
ql is associated with output 1. This means that with input A we get an output
of 1, if the machine starts at state ql' Thus this Moore machine accepts a zerolength sequence (null sequence) which is not accepted by the Mealy machine.
To overcome this situation, either we must neglect the response of a Moore
machine to input A. or we must add a new starting state qQ, whose state
transitions are identical with those of q\ but whose output is O. So Table 3.12
is transformed to Table 3.13.
TABLE 3.13 fv100re Machine of Example 3.9
Present state
a = 0
Next state
a = 1
Output
-'tqo
q3
q2C
q,
q3
q2C
q2C
q,
Q40
q21
q,
q4C
q3
q21
01
q4J
q41
q3
q41
Q4'
q2,
o
1
o
o
o
1
From the foregoing procedure it is clear that if we have an m-output, 11state Mealy machine. the corresponding m-output Moore machine has no more
than 11111 + 1 states.
3.8.3 PROCEDURE FOR TRANSFORMING A MOORE MACHINE
INTO A MEALY MACHINE
We modify the acceptability of input string by a Moore machine by neglecting
the response of the Moore machine to input A. We thus define that Mealy
Machine M and Moore Machine 11;1' are equivalent if for all input strings lV,
b 7 ,t\,w) =Zw(w}. where b is the output of the Moore machine for its initial
state. We give the following result: Let AIL = (Q, L, ll, 8, A.. qo) be a Moore
machine. Then the following procedure may be adopted to construct an
equivalent Mealy machine Mo.