A finite state transducer (FST) is a Finite State Machine that produces outputs in addition to having states. Where a plain FSM just transitions between states based on inputs, a transducer also emits an output symbol at each step — it “translates” or “transduces” an input sequence into an output sequence.
In Turing-machine terminology: the FST reads from an input tape and writes to an output tape. The mapping from input to output is governed by the state transitions and the output rules.
The two flavors of FST are Mealy and Moore — they differ in whether the output depends on (state + input) or just (state).
Mealy and Moore as transducers
A Mealy machine is a transducer whose output is a function of the current state and the current input. Outputs are labeled on the transition arrows in the state diagram.
A Moore machine is a transducer whose output is only a function of the current state. Outputs are labeled inside the state bubbles.
Both compute the same class of input-output mappings — they’re equivalent in expressive power — but their state counts and timing behaviors differ. See Mealy machine and Moore machine for the side-by-side comparison.
Output timing
In a clocked Mealy circuit, outputs can change during a clock cycle (whenever the input changes), creating momentary glitches. To avoid this, inputs are synchronized to the clock so they change only at the inactive edge. The output is sampled just before the active clock edge.
In a Moore circuit, outputs are tied to the state register and change only when the state updates — at the clock edge. No glitches between edges. This is why Moore is preferred when downstream circuits sample the output as a clocked signal.
Conversion between Mealy and Moore
You can convert between the two machine types — useful when the natural specification is in one form but the implementation favors the other.
Mealy → Moore
For every incoming transition with a unique output, duplicate the destination state into intermediate states — one per distinct incoming output. Each new state has the corresponding output baked in.
The resulting Moore machine has more states than the original Mealy (because outputs that varied per input must now have their own states), but every state has a fixed output.
Moore → Mealy
For every state with a fixed output, duplicate that output onto every incoming transition.
The Moore machine’s state count stays the same, but transitions now carry output labels (which they didn’t before).
Worked Mealy → Moore conversion
Mealy “detect two consecutive 1s” with two states:
| State | Next on 0 | Out on 0 | Next on 1 | Out on 1 |
|---|---|---|---|---|
| A | A | 0 | B | 0 |
| B | A | 0 | B | 1 |
The transitions into B carry two different outputs (0 from A on input 1, 1 from B on input 1). Split B into:
- — “in state B with last incoming output 0”.
- — “in state B with last incoming output 1”.
Both and behave like the original B for next-state purposes; they differ only in their fixed Moore output. Rebuilding the table with state-output (Moore) form:
| State | Next on 0 | Next on 1 | Output |
|---|---|---|---|
| A | A | 0 | |
| A | 0 | ||
| A | 1 |
Three states instead of two — the price of moving the output off the transitions. Now is the only state with output 1, exactly the “I have just seen the second 1” state of the standard Moore sequence detector.
For Moore → Mealy, the conversion is one-to-one on states: walk the state table and stamp each state’s output onto every transition that ends at that state. The resulting Mealy machine has the same state count as the Moore.
Why FSTs matter
Finite state transducers show up wherever input is processed sequentially with output produced along the way:
- Parsing: a tokenizer is an FST mapping characters to tokens.
- Compilers: lexical analyzers are FSTs.
- Communication protocols: sender/receiver state machines emit and consume bytes.
- Spell checkers: morphological analyzers map word forms to lemma + tags.
- Text translation: simple word-by-word translators (modern translators use neural networks, not FSTs).
- Hardware control units: control signal sequences for processor pipelines.
The sequence detector in the design example is a Moore-style FST that emits a 1-bit output per cycle.
Beyond FST: pushdown and Turing
FSTs are a special case of a broader hierarchy:
- FST: finite states, input + output tapes. Computes regular transductions.
- Pushdown transducer: adds a stack. Computes context-free languages.
- Turing machine: adds an unbounded read/write tape. Computes anything computable.
Each level adds memory power. FSTs are limited to “memoryless except for finite state” computations — fast, predictable, but unable to handle nested structures (parentheses matching needs a stack, not just states).
For the underlying state machine model, see Finite State Machine. For the two specific implementations, see Mealy machine and Moore machine.