Determinization of Transducers

The determinization algorithm that is used for transducers is a generalization of the algorithm presented. It is based on the algorithm described in Roche and Schabes ([12]). In this generalized version, a state in the determinized transducer is a set of states from the input transducer, where each of these states is associated with a sequence of symbols that still need to be written.

The output of this algorithm is a sub-sequential transducer. We can think of such a transducer as an ordinary transducer, except that a sequence of symbols is associated with each final state. If the system halts in a final state, then the associated symbols are written to the output tape. Such transducers are able to recognize whether or not the end of the string has been reached. Consider, for example, the following transducer. This transducer transduces a string of a's into b's, except for the last a:

start(q0). final(q1). trans(q0,a/b,q2). trans(q2,a/a,q1). jump(q0,q2). jump(q2,q0).

(37)

In order to determinize this transducer, (i.e. ensure that for each state and each symbol there is only a single transition), the extra power of sub-sequential transducers is necessary:

start(q0). final_td(q1,[a]). trans(q0,a/'$E',q1). trans(q1,a/b,q1).

(38)

Even if the input transducer defines a function, it is not always possible to construct such a deterministic (subsequential) transducer. An example of an inherently non-deterministic transducer is given below:

If the system is in state 0 and it reads an a, then it can only decide which transition to take after reading an unbounded number of b's. The algorithm runs into an infinite loop for transducers for which no determinized version exists. ¹