F
Appendix A
Finite-State
Transducers
inite accepters play a central role in the study of formal languages, but
in other areas, such as digital design, transducers are more important.
While we cannot go into this subject matter in any depth, we can at
least outline the main ideas. A full treatment, with many examples of
practical applications, can be found in Kohavi and Jha, 2010.
A.l A General Framework
Finite-state transducers (fst's) have many things in common with finite accepters.
An fst has a finite set Q of internal states and operates in a discrete time frame
with transitions from one state to another made in the interval between two
instances t n and t n+1 . An fst is associated with a read-once-only input file that
contains a string from an input alphabet ∑, and an output mechanism that
produces a string from an output alphabet Γ in response to a given input. It will
be assumed that in each time step one input symbol is used, while a single output
symbol is produced (we also say printed).
Since an fst just translates certain strings into other strings, we can look at
the fst as an implementation of a function. If M is an fst, we will let F M denote
the function represented by M, so
F M : D → R,
where D is a subset of ∑* and R is a subset of Γ*. For most of the discussion we
assume that D = ∑*.
Interpreting an fst as a function implies that it is deterministic, that is, the
Appendix A
Finite-State
Transducers
inite accepters play a central role in the study of formal languages, but
in other areas, such as digital design, transducers are more important.
While we cannot go into this subject matter in any depth, we can at
least outline the main ideas. A full treatment, with many examples of
practical applications, can be found in Kohavi and Jha, 2010.
A.l A General Framework
Finite-state transducers (fst's) have many things in common with finite accepters.
An fst has a finite set Q of internal states and operates in a discrete time frame
with transitions from one state to another made in the interval between two
instances t n and t n+1 . An fst is associated with a read-once-only input file that
contains a string from an input alphabet ∑, and an output mechanism that
produces a string from an output alphabet Γ in response to a given input. It will
be assumed that in each time step one input symbol is used, while a single output
symbol is produced (we also say printed).
Since an fst just translates certain strings into other strings, we can look at
the fst as an implementation of a function. If M is an fst, we will let F M denote
the function represented by M, so
F M : D → R,
where D is a subset of ∑* and R is a subset of Γ*. For most of the discussion we
assume that D = ∑*.
Interpreting an fst as a function implies that it is deterministic, that is, the