In this part of the lecture, we talk about automata which define functions

   

Such automata are called transducers. Examples of functions that we wish to model include:

1.  replace every by
2. duplicate every
3. duplicate every letter at an even-numbered position
4. swap the first and last letter
5. identity if the last letter is , otherwise erase the entire word
6. duplicate the entire word
7. reverse the entire word

The simplest possible model, which has already been discussed in previous lectures, is a deterministic finite automaton over the input alphabet, where every transition is labelled by letter of the output alphabet (this is enough to cover example 1), or a possibly empty word over the output alphabet (this is enough to cover examples 2 and 3).

The remaining examples require additional features. We describe two groups of transducers in the rest of the lecture.

In this lecture, we describe nondeterministic finite automata with output, as well as two other models that have the same expressive power. These models are sufficient to cover examples 4 and 5.

To cover functions like duplication or reverse, much more power is needed. One solution is to use two-way transducers. Another solution is to uses one-way automata with registers. Finally, we show that these solutions are equivalent.