... alphabet.¹

If infinite alphabets are allowed, then certain non-regular languages such as $\{0,1,\dots\}^*$ can be recognized. A similar generalization of regular languages is used by [29].

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... automata.²

Note that in such an implementation, the regular expression operator ? (any symbol) is not to be confused with the special symbol in automata ? (any symbol not occurring in the automaton).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ?.³

Here we assume that we are not explicitly representing states which are not co-accessible, i.e. for which there is no path to a final state.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... transitions:⁴

An implementation might choose to ignore transitions for which the corresponding predicate is not satisfiable.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....⁵

Note that without loss of generality we assume that there is no separate input and output alphabet, nor separate sets of predicates for input and output.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....⁶

As is well-known, not all finite-state transductions can be encoded by a deterministic transducer. As an example, a transduction which maps every a to a b if the input is of even length, and which maps every a to itself otherwise is a finite-state transduction, but cannot be encoded deterministically.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...roch:lang97.⁷

We represent emissions associated with final states, as they surface in the determinization algorithm below, using an extra transition with $\epsilon$ as the domain part. We thus allow transitions $(p,\epsilon,\psi,q)$ only in case q is a final state and there are no transitions leaving q.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... deterministically:⁸

By `writing out deterministically' we mean writing out with a deterministic state transition. Such `deterministic' outputs may still in the end be rejected if for some input, the machine ends in a non-final state.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... symbol.⁹

Of related interest is the approach of [19]. He shows that ambiguous transductions can be computed efficiently by factorizing an ambiguous transducer T into a functional transducer T₁ and an ambiguous transducer T₂ such that T is equivalent to $T_1\circ T_2$, and such that T₂ contains no `failing paths'. In typical cases, T₁ contains meta-symbols which are expanded in T₂. This approach is more general in the sense that these meta-symbols range over sequences of symbols, rather than single symbols. It is more limited in the sense that identities cannot be expressed.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Karttunen¹⁰

personal communication

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... web-site.¹¹

http://www.rxrc.xerox.com/research/mltt/fst/fsexamples.html

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.