Collections
Machines gathered the way a course or a question gathers them.
Arithmetic with automata
Remainders, carries and comparisons: how much arithmetic fits in finite memory, and what needs a stack or a tape. Several of these read numbers least significant digit first, which is often what keeps them small.
Beyond regular
Stacks, counters, queues and tapes: what each kind of memory buys. A stack counts and matches; a queue copies; two stacks are a Turing machine; a tape bounded by its input is exactly the context-sensitive languages.
Busy Beaver Hall of Fame
The champions: for each size, the halting machine that runs longest from a blank tape. Every step count here was checked by running the machine to its halt.
Formats and lexers
What a lexer or a form validator does, one machine at a time: identifiers, numbers, comments, string literals, clock times, IP octets, Roman numerals, keywords — and, one step up, the syntax of an expression.
Nondeterminism: the power to guess
Machines that guess and then check: where the end is, which letter repeats, where the middle of a palindrome lies, which items add up to the target. Some guesses save exponentially many states, some add real power, and some only make a machine easier to write.
Six ways to never halt
One machine for each way the library proves that a Turing machine runs forever, from the cheapest — the run repeats itself — to methods borrowed from the computer-checked proof of BB(5).
The ω-automata zoo
All eight acceptance conditions × determinism: Büchi, co-Büchi, parity and weak, deterministic and not — each checked against an LTL formula, and the languages that tell the classes apart.
Puzzles and games
A puzzle with finitely many positions is a finite automaton: its states are the positions and its words are the move sequences. Solving it is finding an accepted word, and the drawing is often the clearest picture of why the puzzle works.
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.
Specification patterns in LTL
The properties engineers write about systems — response, precedence, alternation, fairness, eventual stability — each as an ω-automaton checked against its LTL formula.
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.
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.
Turing machines that compute
Machines that leave an answer on the tape rather than only accepting: addition and multiplication in unary, increment and counting in binary, copying, reversing and sorting.