Finite-state Transducers

Finite-state transducers are represented using the same conventions we use for finite-state acceptors, except that the symbol part of a transition now is written as a pair In/Out, indicating respectively the symbol that is read and the symbol that is written.

Moreover, the symbol '$E' is used to indicate $\epsilon$, in order to allow transitions in which the input or output symbol is the empty symbol. This implies that there are two ways to define a jump in a finite-state transducer: trans(Q0,'$E'/'$E',Q) is equivalent to jump(Q0,Q). Note that the system does not allow the use of sequences of symbols in transitions (it can be shown that this does not restrict the transductions that can be defined).

A sub-sequential transducer is like a finite-state transducer except that we associate a sequence of symbols with a final state. These symbols are written to the output tape if the system halts in that final state. Such sub-sequential transducers are deterministic with respect to the `in'-part of symbols: for each state there is at most one transition leaving that state upon reading some symbol. Note that we use sub-sequential transducers because the determinization of a finite-state transducer leads to a sub-sequential transducer (Roche and Schabes [12]). Sub-sequential transducers are represented as finite-state transducers, except that we now use a different predicate to indicate the final state with a sequence of symbols:

final_td(State,Symbols)

indicates that State is a final state with associated sequence of symbols Symbols. Symbols is a ground Prolog list of symbols.

Sub-sequential transducers can be used wherever finite-state transducers are allowed.