An Introduction to Formal Languages and Automata, 7th Edition

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₀) be a Mealy machine. Then there exists a state q_i ∈ Q and a w ∈ Σ⁺, such that

$${\delta }^{*}(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

$$\begin{array}{l}F(a^{2n})=a^n{b}^n,\hfill \\ F(a^{2n+1})=a^n{b}^{n+1}.\hfill \end{array}$$

Is there a Mealy machine that implements this function? A few tries quickly suggest that the answer is no.

If there existed such a ...