Definition A.7
Let M be a finite-state transducer implementing the function F M and let L be any
language. Then
T M (L) = {F M (w): w ∈ L}
is the M-translation of L.
Now an fst can generate anyoutput since it can just reproduce input that is
generally not limited. But if the input is a regular language, so is the output.
Theorem A.8
Let M = (Q, ∑, Γ, δ M , θ M , q 0 ) be a Mealy machine and let L be a regular
language. The T M (L) is also regular.
Proof: If L is regular, then there exists a dfa N = (P, ∑, δ N , p 0 , F) such that L =
L(N). From M and N we now construct a finite accepter (possibly
nondeterministic) H = (Q H , ∑, δ H , q H , F H ) as follows:
Q M = { q ij : P i ∈ P, q j ∈ Q}.
If δ N (p i , a) = p k , δ M (q j , a) = ql, and θ M (q j , a) = b, then
The initial state for H will be q 00 and its final state set
F H = {q ij : P i ∈ F, q j ∈ Q}.
Then T H (L) is regular.
To defend this statement, notice first that if
q l ,
then