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