2.2.1 What are Finite State Transducers?

A finite state transducer is a finite state automaton that works on two (or more) tapes.

A finite state transducer essentially is a finite state automaton that works on two (or more) tape s. The most common way to think about transducers is as a kind of ``translating machine''. They read from one of the tapes and write onto the other. This, for instance, is a transducer that translates as into bs:

a:b at the arc means that in this transition the transducer reads a from the first tape and writes b onto the second.

Transducers can, however, be used in other modes than the translation mode as well: in the generation mode transducers write on both tapes and in the recognition mode they read from both tapes. Furthermore, the direction of translation can be turned around: i.e. a:b can not only be read as ``read a from the first tape and write b onto the second tape'', but also as ``read b from the second tape and write a onto the first tape''.

So, the above transducer behaves as follows in the different modes.

• generation mode: It writes a string of as on one tape and a string bs on the other tape. Both strings have the same length.

• recognition mode: It accepts when the word on the first tape consists of exactly as many as as the word on the second tape consists of bs.

• translation mode (left to right): It reads as from the first tape and writes a b for every a that it reads onto the second tape. Try it: testtrans(a2b,[a,a,a],Tape2).

• translation mode (right to left): It reads bs from the second tape and writes an a for every b that it reads onto the first tape.

Transitions in transducers can make jumps going from one state to another without doing anything on either one or on both of the tapes. So, transitions of the form a:# or #:a or #:# are possible. Here is an example:

And what does this transducer do?

• generation mode: It writes twice as many as onto the second tape as onto the first one.

• recognition mode: It accepts when the second tape has twice as many as as the first one.

• translation mode (left to right): It reads as from the first tape and writes twice as many onto the second tape.

• translation mode (right to left): It reads as from the second tape and writes half as many onto the first one. Try it: testtrans(adoubler,Tape1,[a,a,a,a,a,a,a,a]).

Similar as with FSAs, we can also use categories to label the arcs and provide a kind of lexicon which translates these categories into real labels, i.e. labels of the form X:Y. Here is an example translating English number terms into numbers.

And here is the lexicon that maps the category labels to standard FST transition labels:

lex(one:1,`ONES').
lex(two:2,`ONES').
lex(three:3,`ONES').
lex(four:4,`ONES').
...
lex(eleven:11,`TEENS').
lex(twelve:12,`TEENS').
...
lex(twenty:2,`TENS').
lex(twenty:3,`TENS').
...
lex(zero:0,`ZERO').

An implementation of a transducer using such a lexicon can be found in trans_lex.pl . We will not discuss it here in detail. If you have read the next section, you will easily understand it yourself.