A finite state transducer is a 5-tuple (Q,Σ, Γ, δ, q0), where
i) Q is a finite set called the states,
ii) Σ is a finite set called the alphabet,
iii) Γ is a finite set called the output alphabet,
iv) δ : Q × Σ−→Q × Γ is the transition function,
v) q0 ∈ Q is the start state.
Let M = (Q,Σ, Γ, δ, q0) be a finite state transducer, w = w1w2 · · ·wn be a string
over Σ, and v = v1v2 · · · vn be a string over the Γ. Then M outputs v if a sequence of
states r0, r1, . . . , rn exists in Q with the following two conditions:
i) r0 = qo
ii) δ(ri, wi+1) = (ri+1, vi+1) for i = 0, . . . , n − 1.