Library

Collection · 15 machines · curated by @thethinkmachine

Regular languages, start to finish

The finite-memory machines in the order a course meets them: a parity bit, a suffix, a forbidden pattern; then the price of determinism, ε-moves and Thompson’s construction; then two-way heads, which add no power and can save exponentially many states.

Essay

3 min read · 1 figure

A finite automaton has a fixed, finite memory and reads its input once, left to right. That sounds too weak to be interesting, and it is the opposite: the languages these machines recognise — the regular languages — are exactly the ones regular expressions describe, they are closed under every operation anyone cares about, and nearly every question about them can be answered by an algorithm. This collection follows the order a course meets them in.

One bit of memory, then a few

An even number of 1s is the smallest machine whose state means something: it remembers one bit, the parity so far, and the two states are the two possible answers. Ends in 01 remembers how much of a pattern it has just seen, and no two 0s in a row remembers only the last symbol. Two counters side by side give a product: six states in a 3 × 2 grid, each coordinate one of the conditions.

The question to ask of any DFA is what does each state know? If two states know the same thing about the future — if every continuation is accepted from both or from neither — they can be merged. Doing that until nothing more merges gives the minimal DFA, which is unique. A game of tennis is drawn the way an umpire scores and is not minimal: 30–30 and deuce turn out to be the same state, and so do 40–30 and advantage A.

Guessing

A nondeterministic automaton may have several moves on the same symbol, and accepts if any choice leads to acceptance. It adds no power — the subset construction turns any NFA into a DFA — but it can be exponentially smaller.

Figure 1. The same language twice: 4 states that guess where the end is, and 8 that remember instead.

For “the nth symbol from the end is a 1” the NFA needs n + 1 states and the DFA 2ⁿ, and no DFA can do better: two different strings of length n must lead to different states, since some continuation tells them apart. Some letter is missing is the same trade in another form — guess the letter, or remember every letter seen.

ε-moves and regular expressions

A move that reads nothing is the natural way to say or, optionally and and then. a*b*c* is three loops joined by ε-moves; Thompson’s construction builds an ε-NFA from any regular expression by gluing one small gadget per operator, which is how regular-expression engines begin. Going back, from automaton to expression, is state elimination — the app’s To regex does it.

Surprises

Some languages look like they need counting and do not. As many ab’s as ba’s needs no counter at all, because the two counts can never differ by more than one, and they are equal exactly when the word starts and ends with the same letter. An even number of inversions counts something quadratic, but only its parity, and parity is cheap.

Two-way heads

A finite automaton whose head can move both ways recognises no more languages than a one-way one — that is a theorem of Rabin and Scott, and of Shepherdson1 — but it can be far smaller. The fourth symbol from the end needs sixteen states one way and six two ways: run to the end and walk back. Two passes, one head checks two conditions by reading the input twice instead of remembering both at once.

  1. M. O. Rabin and D. Scott, “Finite automata and their decision problems”, IBM Journal 3 (1959); J. C. Shepherdson, “The reduction of two-way automata to one-way automata”, IBM Journal 3 (1959). ↩

The machines

An even number of 1s DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Ends in 01 DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 No two 0s in a row DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 a’s a multiple of 3, b’s even DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 The third symbol from the end is a 1 DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 The third symbol from the end is a 1, by guessing NFA · 4 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Some letter is missing NFA · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 (ab ∪ aba)* NFA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 a’s, then b’s, then c’s ε-NFA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Thompson’s construction of (a|b)*abb ε-NFA · 11 states Tested Added 8 Oct 2026Updated 8 Oct 2026 A game of tennis, won by A DFA · 20 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 As many ab’s as ba’s DFA · 5 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 The fourth symbol from the end, by walking back 2DFA · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Two passes, one head 2DFA · 5 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Déjà vu: the last letter is a rerun 2NFA · 8 states Tested Added 28 Sept 2026Updated 28 Sept 2026