The Moore machine in Figure A.5(a) is equivalent to the Mealy machine in
Figure A.5(b).
Figure A.5
Theorem A.1
For every Moore machine there exists an equivalent Mealy machine.
Proof: Let M = (Q, ∑, Γ, δ M , θ M , q o ) be a Moore machine. We then construct a
Mealy machine N = (Q, ∑, Γ, δ N , θ N , q 0 ), where
δ N = δ M
and
θ N (q i , a) = θ M (δ M (q i , a)).
It is intuitively clear that M and N are equivalent. Both machines go through the
same states in response to a given input. M prints a symbol when a state is
entered, N prints the same symbol during the transition to that state. A more
explicit proof involves an easy induction that we leave to the reader.
The conversion from a Mealy machine to an equivalent Moore machine is a