output is uniquely determined by the input. Nondeterminism is an important
issue in language theory, but plays no significant role in the study of finite-state
transducers.
The rule that one input symbol results in one output symbol appears to imply
that the mapping F M is length-preserving, that is, that
|F M (w)| = |w|.
But this is more apparent than real. For example, we can always include the
empty string λ in Γ, so that
|F M (w)| < |w|
becomes possible. There are other ways in which the length-preserving
restriction can be overcome.
There are several types of fst's that have been extensively studied. The main
difference between them is on how the output is produced.
A.2 Mealy Machines
In a Mealy machine, the output produced by each transition depends on the
internal state prior to the transition and the input symbol used in the transition,
so we can think of the output produced during the transition.
Definition A.1
A Mealy machine is defined by the sextuple
M = (Q, ∑, Γ, δ, θ q 0 ),
where
Q is a finite set of internal states,
∑ is the input alphabet,
Γ is the output alphabet,
δ : Q × E → Q is the transition function,