A.7 Limitations of Finite-State Transducers
Mealy and Moore machines are finite-state automata so we rightly suspect that
their capabilities are limited, just as finite accepters are limited. To explore these
limitations we need something like the pumping lemma for regular languages.
Theorem A.7
Let M = (Q, ∑, Γ, δ, θ, q 0 ) be a Mealy machine. Then there exists a state q i ∈ Q
and a w ∈ ∑+, such that
δ* (q i , w) = q i .
Proof: This follows from the pigeonhole principle, noting that |Q| is finite but w
can be arbitrarily long.
Example A.10
Consider the function F{a}* → {a, b}*, defined by
Is there a Mealy machine that implements this function? A few tries quickly
suggest that the answer is no.
If there existed such a machine with m states, we could pick as input w =
a 2m . During the processing of the first part of this string, by Theorem A.7, the
machine would have to go into a cycle in which an input of a produces an output
of a. To escape from the cycle we would need an input other than a. But since
there is no other input, the machine would continue to print a’s and so not
represent the function. The contradiction shows that no such machine can exist.
The conclusion from this example should not be surprising as it involves
translating a regular set into one that is not regular. In fact, the structural
similarity between fst's and finite accepters suggests a connection between
regular languages and the output produced by finite-state transducers.
Mealy and Moore machines are finite-state automata so we rightly suspect that
their capabilities are limited, just as finite accepters are limited. To explore these
limitations we need something like the pumping lemma for regular languages.
Theorem A.7
Let M = (Q, ∑, Γ, δ, θ, q 0 ) be a Mealy machine. Then there exists a state q i ∈ Q
and a w ∈ ∑+, such that
δ* (q i , w) = q i .
Proof: This follows from the pigeonhole principle, noting that |Q| is finite but w
can be arbitrarily long.
Example A.10
Consider the function F{a}* → {a, b}*, defined by
Is there a Mealy machine that implements this function? A few tries quickly
suggest that the answer is no.
If there existed such a machine with m states, we could pick as input w =
a 2m . During the processing of the first part of this string, by Theorem A.7, the
machine would have to go into a cycle in which an input of a produces an output
of a. To escape from the cycle we would need an input other than a. But since
there is no other input, the machine would continue to print a’s and so not
represent the function. The contradiction shows that no such machine can exist.
The conclusion from this example should not be surprising as it involves
translating a regular set into one that is not regular. In fact, the structural
similarity between fst's and finite accepters suggests a connection between
regular languages and the output produced by finite-state transducers.