Library

Collection · 25 machines · curated by @thethinkmachine

Machines that write

Moore machines print on states, Mealy machines on edges; finite-state transducers may print any string, or guess; pushdown and two-way transducers can reverse. From a thermostat to the shunting-yard algorithm.

Essay

2 min read · 1 figure

An acceptor answers yes or no. A transducer answers with a string: it reads its input and writes an output as it goes, so it computes a function — or, when it is nondeterministic, a relation. The kinds of transducer differ in where the output is attached and in what the machine may remember, and those two choices decide what it can compute.

Moore and Mealy

A Moore machine prints on its states: every state has an output symbol, printed on arrival, so the output is one symbol longer than the input — the start state speaks before anything is read. A thermostat is the clearest example: its output is the heater, and its single bit of memory is the whole reason it does not flicker. A debouncer is the same idea with a longer memory.

A Mealy machine prints on its edges, so its output keeps exact pace with its input and can depend on the symbol just read. That makes it the natural model of a serial circuit: a serial adder carries one bit, two’s complement remembers whether it has passed the first 1, and division by 3 keeps a remainder and prints the quotient. Any Moore machine can be turned into a Mealy machine and back; they differ by a delay of one symbol.

Finite-state transducers

A finite-state transducer may print any string on an edge, including none, and may be nondeterministic. That lets it insert — bit stuffing adds a 0 after five 1s — and substitute strings for letters, as Morse code does with a single state. Nondeterminism lets it look ahead by guessing: replace the last letter bets on where the end is, and thousands separators bets on the length mod 3. Only the branch that guessed right reaches an accepting state, so exactly one output survives.

What a one-way finite transducer cannot do is reverse: it has no way to hold an unbounded amount of input.

Reversal: a stack, or a head that turns

A pushdown transducer reverses by pushing everything and popping it back out, and the same machinery runs the shunting-yard algorithm, which turns infix arithmetic into postfix. A two-way transducer reverses with no memory at all, by reading the input backwards, and can copy its input twice — a function no one-way transducer, with or without a stack, computes.

Figure 1. Output on states, output on edges, output by guessing, output from a stack.

The machines

The running remainder mod 3 Moore · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A thermostat with hysteresis Moore · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A switch debouncer Moore · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Combination lock: 1101 Moore · 5 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Serial binary adder Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Two’s complement, least significant bit first Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Dividing by 3, most significant bit first Mealy · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A Vigenère cipher with the key “bc” Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Binary → Gray code FST · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 HDLC bit stuffing FST · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Morse code for e, t, a, n, i, m, s and o FST · 1 state Tested Added 8 Oct 2026Updated 8 Oct 2026 Thousands separators FST · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Infix to postfix: the shunting-yard algorithm PDT · 7 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Reverse the input PDT · 3 states Tested Added 28 Sept 2026Updated 28 Sept 2026 A word and its mirror: w ↦ wwᴿ 2DFT · 4 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Copy twice: w ↦ ww 2DFT · 5 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Polish notation to reverse Polish PDT · 3 states Tested Added 8 Oct 2026Updated 9 Oct 2026 What is left after cancelling () PDT · 3 states Tested Added 8 Oct 2026Updated 9 Oct 2026 A coin-operated turnstile Moore · 2 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Run-length decoding FST · 3 states Tested Added 28 Sept 2026Updated 9 Oct 2026 Rotate: move the first letter to the end 2DFT · 5 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A traffic light with a pedestrian button Moore · 4 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Strip # comments FST · 2 states Tested Added 28 Sept 2026Updated 9 Oct 2026 A garage door with a safety sensor Moore · 5 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A vending machine that gives change FST · 3 states Tested Added 28 Sept 2026Updated 9 Oct 2026