Library

Collection · 28 machines · curated by @thethinkmachine

From the textbooks: Sipser and Hopcroft–Motwani–Ullman

The machines the two standard textbooks build, with their own state names, each card saying where in the book it comes from. Read alongside the chapter, or run them to see what the diagram on the page does.

Essay

2 min read

Two books have taught most of the people who know this subject. Michael Sipser’s Introduction to the Theory of Computation is the shorter and more conversational; John Hopcroft, Rajeev Motwani and Jeffrey Ullman’s Introduction to Automata Theory, Languages, and Computation — descended from Hopcroft and Ullman’s 1979 book — is the fuller reference. Both open with the same journey, from finite automata through pushdown automata to Turing machines, and both teach it through small machines the reader is meant to trace by hand.

This collection is those machines, with their state names as the books give them, so that the diagram on the page and the one you can run here match. Each card says where in the book it comes from; section numbers rather than example numbers, since those move between editions. The descriptions are ours.

Reading alongside the book

Trace before you run

Each machine accepts a few words on its card and rejects a few. Trace one of each by hand, then press Try it and compare. The run on the diagram is the textbook’s “sequence of states”, drawn.

Sipser, chapter 1 begins with M1, whose language takes a moment to see — a 1, then an even number of 0s after the last one — and goes on through M2 and M3, which differ only in which state accepts, to M5, a running sum with a reset button. The NFAs N1 and N4 are the ones the chapter determinises, and the app’s Subset construction reproduces the book’s result for N4: the states {1,3}, {2}, {2,3}, {3} and {1,2,3} — all but the empty set, which the app leaves out, drawing a missing edge instead.

Hopcroft, Motwani and Ullman, chapter 2 opens with a DFA for 01 and even 0s and even 1s, then introduces nondeterminism with ends in 01 and applies it to text search. Its decimal-number ε-NFA is the standard picture of an ε-move doing the work of “optionally”.

Pushdown automata are represented by aⁿbⁿ, the palindromes both books use to introduce nondeterministic PDAs, Sipser’s i = j or i = k, and Hopcroft, Motwani and Ullman’s if/else, their example of the difference between accepting by final state and by empty stack.

Turing machines: Sipser’s M1, M2 and M3, and Hopcroft, Motwani and Ullman’s 0ⁿ1ⁿ and proper subtraction. Every one of them crosses symbols off and walks back and forth — the technique that makes a single tape do everything.

The dragon book — Aho, Lam, Sethi and Ullman’s Compilers — contributes one more: Thompson’s construction of (a|b)*abb, the ε-NFA from which its lexing chapter builds a DFA by the subset construction — five states, A to E — and then minimises it to four.

The machines

Sipser’s M1: a 1, then an even number of 0s DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Sipser’s M2: ends in 1 DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Sipser’s M3: empty, or ends in 0 DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Sipser’s M4: starts and ends with the same symbol DFA · 5 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Sipser’s M5: a running sum mod 3, with reset DFA · 3 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Contains 001 DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Sipser’s N1: contains 101 or 11 ε-NFA · 4 states Tested Added 28 Sept 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 Sipser’s N3: unary lengths divisible by 2 or 3 ε-NFA · 6 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Sipser’s N4: the NFA converted in the text ε-NFA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 aⁿbⁿ DPDA · 4 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 aⁱbʲcᵏ with i = j or i = k NPDA · 6 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Palindromes: guess the middle NPDA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Two equal halves: w#w TM · 9 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Sipser’s M2: 0s whose number is a power of 2 TM · 6 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Multiplication checked: aⁱbʲcᵏ with k = i·j TM · 14 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Contains 01 DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 An even number of 0s and an even number of 1s DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Ends in 01, by guessing NFA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Finding “web” or “ebay” NFA · 8 states Tested Added 8 Oct 2026Updated 8 Oct 2026 A decimal number, with ε-moves ε-NFA · 6 states Tested Added 8 Oct 2026Updated 8 Oct 2026 One else too many DPDA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 0ⁿ1ⁿ by crossing off TM · 5 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Proper subtraction: m ∸ n TM · 8 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Thompson’s construction of (a|b)*abb ε-NFA · 11 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Sipser’s M4: are the strings all different? TM · 17 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Every window of five has two 0s DFA · 15 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Turing’s first machine: 0 1 0 1 … ITM · 4×3 · never halts Deterministic Added 28 Sept 2026Updated 9 Oct 2026