An Introduction to Formal Languages and Automata, 7th Edition

A.1 A GENERAL FRAMEWORK

Finite-state transducers (fst’s) have many things in common with finite accepters. An fst has a finite set Q of internal states and operates in a discrete time frame with transitions from one state to another made in the interval between two instances t_n and t_n+1. An fst is associated with a read-once-only input file that contains a string from an input alphabet Σ, and an output mechanism that produces a string from an output alphabet Γ in response to a given input. It will be assumed that in each time step one input symbol is used, while a single output symbol is produced (we also say printed).

Since an fst just translates certain strings into other strings, we can look at the fst as an implementation of a function. ...