Library

A catalogue of automata,
tested before they’re listed.

Finite and ω-automata, pushdown and Turing machines, transducers — each with its diagram, its language and its formal definition, and each one click from your canvas.

259 machines · 13 collections · How they are checked

q0q1q20, R12012, R01, R2
Sipser’s M5: a running sum mod 3, with reset, DFA, minimal. Every figure in the library is drawn from the machine’s own file.

Recently added

All →

Recently updated

All →

Busy Beaver Hall of Fame

All 7 →

From the textbooks: Sipser and Hopcroft–Motwani–Ullman

All 28 →

Regular languages, start to finish

All 15 →

Puzzles and games

All 13 →

The ω-automata zoo

All 16 →

Collections

All 13 →
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. 16 machines · curated by @thethinkmachine 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. 20 machines · curated by @thethinkmachine 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. 7 machines · curated by @thethinkmachine 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. 20 machines · curated by @thethinkmachine 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. 13 machines · curated by @thethinkmachine 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). 6 machines · curated by @thethinkmachine

Every machine

259 machines

(ab ∪ aba)* NFA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 (ab)* with noise DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 0ⁿ1ⁿ by crossing off TM · 5 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 3-tape adder — one pass MTM · 3 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 4-tape ALU — add, and, or, xor, not MTM · 8 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Diagram of A 198-state machine that halts only if set theory C₀ is inconsistent A 198-state machine that halts only if set theory C₀ is inconsistent ITM · 199 states Deterministic Added 12 Nov 2026Updated 12 Nov 2026 A 2 × 2 sliding puzzle DFA · 12 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A 24-hour clock time, HH:MM DFA · 7 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A binary counter that never stops ITM · 3×2 · never halts Deterministic Added 28 Sept 2026Updated 9 Oct 2026 A byte in decimal: 0 to 255 DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A byte with even parity DFA · 18 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A C comment, /* … */ DFA · 5 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A C integer literal: decimal, octal or hex DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A checkerboard pyramid ITM · 3×2 · never halts Deterministic Added 28 Sept 2026Updated 9 Oct 2026 A coin-operated turnstile Moore · 2 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 A copy, with a stack of stacks: w#w EPDA · 5 states Tested Added 28 Sept 2026Updated 9 Oct 2026 A CSV record with quoted fields DFA · 4 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A decimal number, with ε-moves ε-NFA · 6 states Tested Added 8 Oct 2026Updated 8 Oct 2026 A full IPv4 address DFA · 24 states Tested · Minimal · Deterministic Added 9 Oct 2026Updated 9 Oct 2026 A game of tennis, won by A DFA · 20 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A garage door with a safety sensor Moore · 5 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A gene, start codon to stop codon DFA · 10 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A halt nothing leads to ITM · 3×2 · never halts Deterministic Added 28 Sept 2026Updated 28 Sept 2026 a happens at least twice DWA · 3 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 a happens, eventually DWA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A hex colour: #rgb or #rrggbb DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A keyword: if, in, int or for DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A knight on a 3 × 3 board DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A microwave oven’s door interlock DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 A nested list: [x;[x;x];[]] DPDA · 6 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A number in scientific notation DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A palindrome with its middle marked: wcwᴿ DPDA · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A password with a letter, a digit and a symbol DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A phone number, area code optional ε-NFA · 14 states Tested Added 8 Oct 2026Updated 8 Oct 2026 A robot that comes home DFA · 9 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A string literal with escapes DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A switch debouncer Moore · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 A thermostat with hysteresis Moore · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A three-bit linear-feedback shift register Moore · 7 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 A traffic light with a pedestrian button Moore · 4 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 A valid expression in reverse Polish notation Counter · 4 states Tested Added 28 Sept 2026Updated 8 Oct 2026 A vending machine that gives change FST · 3 states Tested Added 28 Sept 2026Updated 9 Oct 2026 A Vigenère cipher with the key “bc” Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A word and its mirror: w ↦ wwᴿ 2DFT · 4 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 A word repeated twice: ww LBA · 10 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 a, then later b, then later c DFA · 4 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 a’s a multiple of 3, b’s even DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 a’s, then b’s, then c’s ε-NFA · 3 states Tested 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 aⁱbʲcᵏ with i = j or j = k NPDA · 9 states Tested Added 8 Oct 2026Updated 8 Oct 2026 An a in every odd position DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 An a, and no b ever after it DWA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 An elevator’s floor display Moore · 4 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 An email address, roughly DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 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 An even number of 0s, or exactly two 1s DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 An even number of 1s DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 An even number of a’s, or an odd number of b’s ε-NFA · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 An even number of inversions DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 An identifier DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 An ISO date, YYYY-MM-DD DFA · 14 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 aⁿbᵐ with n ≠ m Counter · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 aⁿbⁿ DPDA · 4 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 aⁿbⁿ or aⁿb²ⁿ NPDA · 6 states Tested Added 8 Oct 2026Updated 8 Oct 2026 aⁿbⁿcⁿ — beyond one stack 2PDA · 4 states Tested Added 28 Sept 2026Updated 28 Sept 2026 aⁿbⁿcⁿ in one pass, with two tapes MTM · 5 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 aⁿbⁿcⁿ in the space of its input LBA · 11 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 aⁿbⁿcⁿ with a queue QA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 aⁿbⁿcⁿdⁿ — four counts, one stack of stacks EPDA · 6 states Tested Added 28 Sept 2026Updated 28 Sept 2026 As many a’s as b’s, in any order DPDA · 3 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 As many a’s as b’s, with one counter Counter · 5 states Tested Added 8 Oct 2026Updated 9 Oct 2026 As many ab’s as ba’s DFA · 5 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 At least two 0s and at most one 1 DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 At most two requests, ever DBA · 3 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Balanced parentheses without a stack TM · 5 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Balanced parentheses, with a second tape for a stack MTM · 6 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Bank account: never overdrawn Counter · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Base64 length and padding DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 BB(2,3) champion ITM · 2×3 · halts in 38 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(2,4) champion ITM · 2×4 · halts in 3.93M Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(2) champion ITM · 2×2 · halts in 6 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(3) champion — most ones ITM · 3×2 · halts in 14 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(3) champion — most steps ITM · 3×2 · halts in 21 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(4) champion ITM · 4×2 · halts in 107 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(5) champion ITM · 5×2 · halts in 47.2M Deterministic Added 28 Sept 2026Updated 28 Sept 2026 BB(6) champion: runs longer than 2↑↑↑5 steps ITM · 6×2 Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Between n and 2n b’s: aⁿbᵐ, n ≤ m ≤ 2n NPDA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Between q and r, p must happen DBA · 3 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Binary → Gray code FST · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Binary addition a+b TM · 8 states · halts in 1 Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Binary divisibility by 3 DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Binary divisibility by 5 DFA · 5 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Binary increment ITM · 3 states · halts in 2 Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Binary multiples of 6, in four states DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Binary numbers greater than 5 DFA · 5 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Binary to unary: counting down ITM · 8 states · halts in 2 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Both a and b, infinitely often DBA · 3 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Bracket matcher ( ) [ ] { } DPDA · 1 state Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Černý’s automaton: one word that resets everything DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Checking a sum, column by column DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Classic: aⁿbⁿ ↦ bⁿaⁿ PDT · 3 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Classic: eventually always b NBA · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Classic: Rabin's cut-point language PFA · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Classic: reverse the input 2DFT · 4 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Combination lock: 1101 Moore · 5 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Comparing two binary numbers, column by column 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 Contains 01 DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Contains a square of length 4 NFA · 12 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Contains both aa and bb DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Copy a string: w ↦ w#w TM · 10 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Copy twice: w ↦ ww 2DFT · 5 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Counting to n in binary ITM · 5 states · halts in 2 Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Cross-serial dependencies: aⁿbᵐcⁿdᵐ EPDA · 6 states Tested Added 8 Oct 2026Updated 9 Oct 2026 Decimal multiples of 3: the digit-sum rule DFA · 3 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Decimal multiples of 5: only the last digit counts DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Decoding a prefix code DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Déjà vu, without guessing 2DFA · 10 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Déjà vu: the last letter is a rerun 2NFA · 8 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Detecting 101, overlaps allowed Mealy · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Dividing by 3, most significant bit first Mealy · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Ends in 01 DFA · 3 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 Even numbers in base 3 DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Eventually always b DcoBA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Eventually always b, by priority DPA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Eventually always b, with a needless guess NcoBA · 3 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Eventually it stops changing DcoBA · 4 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Eventually, a and b alternate forever NBA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Eventually, every a is followed by b DcoBA · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Every a is followed by a b DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Every block of a’s has even length DFA · 2 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Every palindrome, odd or even NPDA · 3 states Tested Added 28 Sept 2026Updated 9 Oct 2026 Every request is eventually granted DBA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Every window of five has two 0s DFA · 15 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Exact change: 30¢ in nickels, dimes and quarters DFA · 7 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Exactly one of a and b, infinitely often NPA · 5 states Tested Added 8 Oct 2026Updated 9 Oct 2026 Exactly two b’s DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Finding “web” or “ebay” NFA · 8 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Finding the EcoRI site GAATTC in DNA DFA · 7 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Float regex, compiled ε-NFA · 5 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Gray code back to binary Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 HDLC bit stuffing FST · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Infinitely many a’s, and eventually no b NBA · 3 states Tested Added 8 Oct 2026Updated 9 Oct 2026 Infinitely many a’s, or finitely many b’s NBA · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Infinitely often a DBA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Infinitely often a, or eventually always c NPA · 5 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Infinitely often, two a’s in a row DBA · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Infix to postfix: the shunting-yard algorithm PDT · 7 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Irregular growth, closed under n-grams ITM · 4×2 · never halts Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Is n a perfect square? 1 + 3 + 5 + … ITM · 15 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Is n composite? Guess a factor NDTM · 8 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Is v a rotation of w? w#v QA · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Diagram of K215: a 215-state machine that halts only if ZFC is inconsistent K215: a 215-state machine that halts only if ZFC is inconsistent ITM · 216 states Deterministic Added 12 Nov 2026Updated 12 Nov 2026 Keyword search: cat | car | cab NFA · 4 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Lengths divisible by 2 or by 3 DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Lengths that are multiples of 3 or of 5 NFA · 9 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Letters alternate DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Lights Out on a 2 × 2 board DFA · 16 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Marching right forever ITM · 3×2 · never halts Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Measuring 4 litres with 3- and 5-litre jugs DFA · 16 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 MFM encoding: between two 1s, one to three 0s DFA · 5 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Missionaries and cannibals DFA · 16 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 More a’s than b’s: aⁿbᵐ, n > m DPDA · 5 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Morse code for e, t, a, n, i, m, s and o FST · 1 state Tested 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 Nested counts: aⁿbᵐcᵐdⁿ DPDA · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Never contains 110 DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Never contains aba DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Never two a's in a row DBA · 3 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Never two a's, with a needless guess NWA · 4 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Nim with five sticks DFA · 8 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 No grant before the first request DBA · 2 states Tested · 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 Noisy channel: does it end in a? PFA · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Not a word repeated twice NPDA · 10 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Once bb, never aa DFA · 4 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 One else too many DPDA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Palindromes in linear time MTM · 5 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Palindromes on one tape TM · 7 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Palindromes: guess the middle NPDA · 3 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Parentheses nested at most three deep DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Penney’s game: HHT before HTT DFA · 5 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Perfect copy: w#w QA · 2 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Polish notation to reverse Polish PDT · 3 states Tested Added 8 Oct 2026Updated 9 Oct 2026 Powers of two in binary DFA · 2 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Powers of two, by halving LBA · 6 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Proper subtraction: m ∸ n TM · 8 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Replace the last letter with x FST · 2 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Requests and grants alternate DBA · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Reverse a string TM · 14 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Reverse every word PDT · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Reverse the input PDT · 3 states Tested Added 28 Sept 2026Updated 28 Sept 2026 Rolling a die until 6 is on top DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Roman numerals from I to MMMCMXCIX DFA · 19 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Rotate: move the first letter to the end 2DFT · 5 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Run-length decoding FST · 3 states Tested Added 28 Sept 2026Updated 9 Oct 2026 Say every letter twice TM · 12 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Searching for a pattern: p#t MTM · 7 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Serial binary adder Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Shuffling three cards DFA · 6 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 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: 0s whose number is a power of 2 TM · 6 states · halts in 1 Tested · Deterministic Added 8 Oct 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: are the strings all different? TM · 17 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 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 Sipser’s N1: contains 101 or 11 ε-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 Some letter is missing NFA · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Some letter occurs twice NFA · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Sort the 0s before the 1s TM · 7 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Sorting by passes: all a’s, then all b’s 2DFT · 5 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Squeeze repeated letters: tr -s FST · 3 states Tested Added 28 Sept 2026Updated 9 Oct 2026 Starts with 0 and has odd length, or starts with 1 and even length DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Starts with 1 and ends with 0 DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Strip # comments FST · 2 states Tested Added 28 Sept 2026Updated 9 Oct 2026 Strong fairness: GF a → GF b DPA · 3 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Subset sum, by guessing NDTM · 11 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Sums of 3s and 5s DFA · 9 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 The account goes overdrawn Counter · 2 states Tested Added 28 Sept 2026Updated 9 Oct 2026 The fourth symbol from the end, by walking back 2DFA · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 The last letter has appeared before NFA · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 The life of a process DFA · 5 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 The parity condition itself DPA · 4 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 The running remainder mod 3 Moore · 3 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 The syntax of an arithmetic expression DPDA · 4 states Tested · 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 Thompson’s construction of (a|b)*abb ε-NFA · 11 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Thousands separators FST · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Three copies: w#w#w QA · 4 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Three wrong passwords and you are out DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Times three, serially Mealy · 6 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Towers of Hanoi, three disks DFA · 27 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Try until it works: amplification PFA · 2 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Turing’s first machine: 0 1 0 1 … ITM · 4×3 · never halts Deterministic Added 28 Sept 2026Updated 9 Oct 2026 Twice as many b’s: aⁿb²ⁿ DPDA · 4 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Two a’s exactly three apart NFA · 5 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Two balanced blocks: 0ⁿ1ⁿ0ᵐ1ᵐ DPDA · 7 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Two cells, forever ITM · 3×2 · never halts Deterministic Added 28 Sept 2026Updated 28 Sept 2026 Two different words: x#y with x ≠ y NPDA · 11 states Tested Added 8 Oct 2026Updated 9 Oct 2026 Two equal halves: w#w TM · 9 states · halts in 1 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 Two processes, one critical section DFA · 3 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Two stacks make a queue: w#w 2PDA · 4 states Tested Added 28 Sept 2026Updated 8 Oct 2026 Two’s complement, least significant bit first Mealy · 2 states Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Unary addition TM · 4 states · halts in 1 Tested · Deterministic Added 28 Sept 2026Updated 8 Oct 2026 Unary addition: aⁱbʲcⁱ⁺ʲ DPDA · 5 states Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Unary multiplication TM · 12 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 8 Oct 2026 Unary remainder: a mod b ITM · 12 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Unbalanced parentheses DPDA · 4 states Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Well-formed UTF-8 DFA · 4 states Tested · Minimal · Deterministic Added 28 Sept 2026Updated 9 Oct 2026 What is left after cancelling () PDT · 3 states Tested Added 8 Oct 2026Updated 9 Oct 2026 Which binary number is smaller? x#y TM · 14 states · halts in 1 Tested · Deterministic Added 8 Oct 2026Updated 9 Oct 2026 Within one typo of “cat” ε-NFA · 8 states Tested Added 8 Oct 2026Updated 8 Oct 2026 Wolf, goat and cabbage DFA · 10 states Tested · Minimal · Deterministic Added 8 Oct 2026Updated 8 Oct 2026