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.

### Sites 6

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]

Last update:

January 2, 2007 at 19:58:46 UTC
Copyright © 1998-2016 AOL Inc.

Built by CMBuild