Transducers are automata that have transitions labeled with two symbols. One of the symbols represents input, the other output. Transducers translate (or transduce) strings. In automata theory they are called Mealy machines.
Finite state transducers recognize tuples of strings. A set of tuples of strings that can be recognized by an FST is called a regular relation. So, regular relations are to FSTs what regular languages are to FSA.
More information
More information
Sites 4
A paper reviewing some of the major applications of FST in natural-language processing ranging from morphological analysis to finite-state parsing.
Lecture notes on FST and their use in building parsers with examples implemented in Prolog.
Wikipedia article with a formal definition and discussion of operators on FST.
A set of slides on finite state transducers, their connection to regular relations and examples of their closure properties.
Lecture notes on FST and their use in building parsers with examples implemented in Prolog.
Wikipedia article with a formal definition and discussion of operators on FST.
A paper reviewing some of the major applications of FST in natural-language processing ranging from morphological analysis to finite-state parsing.
A set of slides on finite state transducers, their connection to regular relations and examples of their closure properties.
