Package nltk_lite :: Package contrib :: Package fst :: Module fst
[hide private]
[frames] | no frames]

Module fst

source code

Finite state transducers.

A finite state trasducer, or FST, is a directed graph that is used to encode a mapping from a set of input strings to a set of output strings. An input string is a sequence of immutable values (such as integers, characters, or strings) called input symbols. Similarly, an output string is a sequence of immutable values called output symbols. Collectively, input strings and output strings are called symbol strings, or simply strings for short. Note that this notion of string is different from the python string type -- symbol strings are always encoded as tuples of input or output symbols, even if those symbols are characters. Also, note that empty sequences are valid symbol strings.

The nodes of an FST are called states, and the edges are called transition arcs or simply arcs. States may be marked as final, and each final state is annotated with an output string, called the finalizing string. Each arc is annotated with an input string and an output string. An arc with an empty input string is called an epsilon-input arc; and an arc with an empty output string is called an epsilon-output arc.

The set of mappings encoded by the FST are defined by the set of paths through the graph, starting at a special state known as the initial state, and ending at a final state. In particular, the FST maps an input string X to an output string Y iff there exists a path from the initial state to a final state such that:

The following list defines some terms that apply to finite state transducers.

An FSA can be represented as an FST that generates no output symbols.

The current FST class does not provide support for:

Possible future changes:

Classes [hide private]
    Finite State Transducer
  FST
A finite state transducer.
    AT&T fsmtools Support
  FSMTools
A class used to interface with the AT&T fsmtools package.
    Graphical Display
  FSTWidget
  FSTDisplay
  FSTDemo