Let C 1 and C 2 be two classes of finite-state transducers. We say that C 1 and C 2
are equivalent if for every fst M in one class there exists an equivalent fst N in
the other class, and vice versa.
We will now show that the Mealy and Moore machine classes are equivalent.
For this we need to introduce the extended transition function δ* and the
extended output function θ*. The expression
δ* (q i , w) = q j
is meant to indicate that the fst goes from state q i to state q j while processing the
string w. Similarly,
θ* (q j , w) = v
is to show that the fst produces output v when starting in state q i and given input
w. For both Mealy and Moore machines δ* is formally defined by
for all a ∈ ∑ and all w ∈ ∑ + . For Mealy machines
while for Moore machines
The conversion of a Moore machine to an equivalent Mealy machine is
straightforward. The states of the two machines are the same, and the symbol
that is to be printed by the Moore machine is assigned to the Mealy machine
transition that leads to that state.
Example A.5