... alphabet.1
If infinite alphabets are allowed, then certain non-regular languages such as can be recognized. A similar generalization of regular languages is used by [29].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... automata.2
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).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... ?.3
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:4
An implementation might choose to ignore transitions for which the corresponding predicate is not satisfiable.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....5
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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

....6
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.7
We represent emissions associated with final states, as they surface in the determinization algorithm below, using an extra transition with as the domain part. We thus allow transitions only in case q is a final state and there are no transitions leaving q.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... deterministically:8
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.9
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 T1 and an ambiguous transducer T2 such that T is equivalent to , and such that T2 contains no failing paths'. In typical cases, T1 contains meta-symbols which are expanded in T2. 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.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Karttunen10
personal communication
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... web-site.11
http://www.rxrc.xerox.com/research/mltt/fst/fsexamples.html
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
`