A finite-state transducer (FST) is a finite-state machine that defines a relation between two languages rather than simply accepting or rejecting strings. Each transition reads a symbol from the input tape and writes a symbol to the output tape, thereby transforming one string into another. FSTs are the most important computational device in morphological and phonological processing, where they model the mapping between surface forms of words and their underlying lexical representations.
Formal Definition and Types
Formally, an FST is defined as T = (Q, Σ, Δ, δ, q₀, F), where Q is a finite set of states, Σ is the input alphabet, Δ is the output alphabet, δ is the transition relation mapping state-input pairs to sets of state-output pairs, q₀ is the initial state, and F is the set of final states. An FST is deterministic if for each state and input symbol there is at most one transition; however, unlike finite-state acceptors, deterministic FSTs are strictly less powerful than nondeterministic ones for defining string relations.
The composition T₁ ∘ T₂: Σ* → Ω* maps input directly to output:
(T₁ ∘ T₂)(w) = T₂(T₁(w))
Composition is closed for rational relations and computable in O(|T₁| × |T₂|).
Applications in Morphology and Phonology
The dominant application of FSTs in computational linguistics is morphological analysis. Kimmo Koskenniemi's two-level morphology models the relationship between lexical (underlying) and surface representations as a regular relation implemented by FSTs operating in parallel. The Xerox finite-state toolkit, developed by Beesley and Karttunen, extended this approach with a rich algebra of transducer operations — composition, intersection, inversion — allowing complex morphological grammars to be compiled into single, efficient transducers.
Phonological rules can be compiled into FSTs following the seminal work of Ronald Kaplan and Martin Kay (1994). Each ordered phonological rule is compiled into a transducer, and the cascade of rules is implemented by transducer composition. The result is a single transducer that applies all rules simultaneously, enabling efficient generation and analysis. This approach elegantly handles rule ordering, feeding, bleeding, and counterbleeding interactions.
Regular Relations and Closure Properties
FSTs define the class of rational (regular) relations over strings. Unlike regular languages, rational relations are not closed under intersection or complementation. However, they are closed under union, composition, concatenation, and Kleene closure. The asymmetry in closure properties has practical implications: while individual morphological rules can be composed, the intersection of two arbitrary transductions cannot in general be computed, requiring workarounds in grammar design.
Beyond morphology, FSTs are used in grapheme-to-phoneme conversion, transliteration between scripts, text normalization, and speech recognition lattice processing. The OpenFST library provides efficient implementations supporting weighted transducers that combine the relational power of FSTs with probabilistic scoring, making them integral to modern speech and language processing pipelines.