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
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.