A finite-state transducer is a device similar to a finite state automaton, but whose purpose is to transform input strings into output strings rather than accept a language. Such a device starts in a designated initial state, and moves from state to state according to the current input just like a finite automaton. However, it also emits a finite string of symbols at each transition according to the current state and current input. We represent such a transducer just as we represent a finite automaton, except that a transition labeled a in a finite automaton is now labeled a/, where is the string emitted when the corresponding transition is performed. For example, the following deterministic finite state transducer outputs all the bs in the input as double cs (that is, cc) and also omits every other a from the output.

1. A finite-state transducer is a device similar to a finite state automaton, but whose purpose is to transform input strings into output strings rather than accept a language. Such a device starts in a designated initial state, and moves from state to state according to the current input just like a finite automaton. However, it also emits a finite string of symbols at each transition according to the current state and current input. We represent such a transducer just as we represent a finite automaton, except that a transition labeled a in a finite automa- ton is now labeled a/a, where is the string emitted when the corresponding transition is performed. For example, the following deterministic finite state transducer outputs all the in the input as double c's (that is, cc) and also omits every other a from the output ala ale Note in particular that the output of a transition (a in the description above) can be a string, not just a symbol. The string will however be finite since its length (and also its content) is fixed in the transition function. Formally (and carefully) define: (a) A deterministic finite state transducer. (b) A configuration of such a transducer. (c) The "yields in one step" relation between configurations. (d) The notion that such a transducer produces output u on input u. (e) The notion that such a transducer computes a function. 1. A finite-state transducer is a device similar to a finite state automaton, but whose purpose is to transform input strings into output strings rather than accept a language. Such a device starts in a designated initial state, and moves from state to state according to the current input just like a finite automaton. However, it also emits a finite string of symbols at each transition according to the current state and current input. We represent such a transducer just as we represent a finite automaton, except that a transition labeled a in a finite automa- ton is now labeled a/a, where is the string emitted when the corresponding transition is performed. For example, the following deterministic finite state transducer outputs all the in the input as double c's (that is, cc) and also omits every other a from the output ala ale Note in particular that the output of a transition (a in the description above) can be a string, not just a symbol. The string will however be finite since its length (and also its content) is fixed in the transition function. Formally (and carefully) define: (a) A deterministic finite state transducer. (b) A configuration of such a transducer. (c) The "yields in one step" relation between configurations. (d) The notion that such a transducer produces output u on input u. (e) The notion that such a transducer computes a function