machine. We then construct a Moore machine M = (Q M , ∑, Γ, δ M , θ M , q 0r ) as
follows: Create the states and the output function of M by
q ia ∈ Q M
and
θ M (q ia ) = a,
for all i = 1, 2,…, n and all a ∈ Γ. For every transition rule
δ N (q i , a) = q j
and corresponding output function
θ N (q i , a) = b
we introduce |Γ| rules
δ M (q ic , a) = q jb
for all c ∈ Γ. Since the start state symbol is not printed before the first transition,
the initial state for M can be any state q 0r , r ∈ Γ. This completes the
construction.
To show that N and M are equivalent, we first show that if
then there is a c ∈ Γ such that
This, and its converse, can be proved by an induction on the length of w.
Next consider
and suppose that
Then