Home | Trees | Indices | Help |
|
---|
|
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:
|
|||
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 |
Home | Trees | Indices | Help |
|
---|
Generated by Epydoc 3.0beta1 on Wed May 16 22:47:17 2007 | http://epydoc.sourceforge.net |