DFSTs

A DFST, or deterministic finite-state transducer, is a type of finite-state machine that reads an input string and produces an output string. It is a deterministic variant of a finite-state transducer in which, for every state and input symbol, there is at most one defined transition and a unique corresponding output, ensuring a single computation path for any given input.

Formally, a DFST is a 6-tuple (Q, Σ, Γ, δ, λ, q0), where Q is a finite set of states, Σ is the input alphabet, Γ is the output alphabet, δ: Q × Σ → Q is the deterministic transition function, λ: Q × Σ → Γ* is the output function that emits a (possibly empty) string on each transition, and q0 ∈ Q is the start state. To process an input word a1 a2 ... an, the machine starts in q0 and, for each symbol ai, follows δ and outputs the string λ(q, ai). The overall output is the concatenation of the per-transition outputs along the run. Some definitions include an initial or final output, but the common form generates output only through transitions.

Determinism guarantees a unique computation path for each input, which simplifies reasoning and implementation compared with nondeterministic transducers. DFSTs realize relations from Σ* to Γ*, and when the relation is functional, each input word has a single associated output word.

DFSTs are related to Mealy and Moore machines (both emit outputs, but Mealy outputs on transitions and Moore on states). They are used in lexical analysis, morphological and phonological processing, text normalization, transliteration, and other string transformation tasks where a regular, rule-based mapping is required.