From (A.2) and
δ M (q kc , a) = q lb
it follows that
Returning now to (A.3)
If we now make the inductive assumption
for all |w| ≤ m and any r ∈ Γ then
and so (A.4) holds for all m.
Putting the two constructions together we get the fundamental equivalence
result.
Theorem A.3
The classes of Mealy machines and Moore machines are equivalent.
A.5 Mealy Machine Minimization
For a given function ∑* → Γ* there are many equivalent finite-state transducers,
some of them differing in the number of internal states. For practical reasons it is
often important to find the minimal fst, that is, the machine with the smallest