little more complicated because the states of the Moore machine now have to
carry two pieces of information: the internal state of the corresponding Mealy
machine, and the output symbol produced by the Mealy machine's transition to
that state. In the construction we create, for each state q i of the Mealy machine, |
Γ| states of the Moore machine labeled q ia , a ∈ Γ. The output function for the
Moore machine states will be θ(q ja ) = a. When the Mealy machine changes to
state q j and prints a, the Moore machine will go into state q ja and so print a also.
Example A.6
The Mealy machine in Figure A.6(a) and the Moore machine in Figure A.6(b)
are equivalent.
Figure A.6
Theorem A.2
For every Mealy machine N there exists an equivalent Moore machine M.
Proof: Let N = (Q N , ∑, Γ, δ N , θ N , q o ) with Q N = {q o , q 1 ,…., q n } be a Mealy