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.
Applications of Finite-State Transducers in Natural-Language Processing
A paper reviewing some of the major applications of FST in natural-language processing ranging from morphological analysis to finite-state parsing.
Finite State Parsers and Transducers
Lecture notes on FST and their use in building parsers with examples implemented in Prolog.
Finite State Transducers
Definition of FST with examples of simple transducers.
Finite State Transducers
Wikipedia article with a formal definition and discussion of operators on FST.
Finite-state Transducers
A set of slides on finite state transducers, their connection to regular relations and examples of their closure properties.
Parsing With Finite State Transducers
A paper that shows how FST can be used to describe complex sytactic structures and provide tools to increase parsing efficiency. [PDF]
[Computer Mozilla]
Last update:
January 2, 2007 at 19:58:46 UTC
Computers
Games
Health
Home
News
Recreation
Reference
Regional
Science
Shopping
Society
Sports
All Languages
Arts
Business