FST

Finite-state transducer (FST) is a computational model that reads an input string and produces an output string, thereby realizing a relation between input and output languages. An FST consists of a finite set of states, a finite input alphabet, a finite output alphabet, transitions that consume input symbols and generate output strings (possibly empty), an initial state, and a set of accepting states. Transitions can be deterministic or nondeterministic, and an FST may be functional (each input string maps to at most one output string) or non-functional.

In conventional form, an FST processes a string by following a path through its states, emitting output along transitions as it consumes input. Some variants distinguish input-only and output-only labels; others use a combined input/output label on each transition. FSTs can be extended with epsilon transitions (producing or consuming no input or output) and can be weighted to associate costs or probabilities with paths. They are capable of representing regular relations, meaning the set of input-output pairs recognized by an FST is regular in a formal sense.

Deterministic FSTs (DFSTs) have at most one valid path for a given input, while nondeterministic FSTs (NFSTs) may have multiple valid paths. In practice, deterministic and functional FSTs are common for practical text processing tasks, while nondeterministic variants are useful in modeling ambiguous phenomena.

Applications of FSTs include morphological analysis and synthesis, grapheme-to-phoneme conversion, transliteration, spelling correction, and text normalization. They underpin many natural language processing pipelines and can be composed with other automata to build complex linguistic tools. Popular software libraries for working with FSTs include OpenFst and FOMA, which support construction, composition, minimization, and weighted variants. Limitations include finite memory restrictions, which constrain long-range dependencies beyond the model’s capacity.