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.
Recently added
All →Recently updated
All →Busy Beaver Hall of Fame
All 7 →
BB(2) champion
ITM · 2×2 · halts in 6
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(3) champion — most ones
ITM · 3×2 · halts in 14
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
From the textbooks: Sipser and Hopcroft–Motwani–Ullman
All 28 →
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
Regular languages, start to finish
All 15 →
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
Puzzles and games
All 13 →
Wolf, goat and cabbage
DFA · 10 states
Tested · Minimal · 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
Lights Out on a 2 × 2 board
DFA · 16 states
Tested · Minimal · Deterministic
Added 8 Oct 2026Updated 8 Oct 2026
Shuffling three cards
DFA · 6 states
Tested · Minimal · Deterministic
Added 8 Oct 2026Updated 8 Oct 2026
The ω-automata zoo
All 16 →
Infinitely often a
DBA · 2 states
Tested · Deterministic
Added 28 Sept 2026Updated 8 Oct 2026
Every request is eventually granted
DBA · 2 states
Tested · 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
Classic: eventually always b
NBA · 2 states
Tested
Added 28 Sept 2026Updated 28 Sept 2026
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.
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).
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
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
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
No machine matchesTry fewer words or clear a filter — or build it and submit it, and it will be the first.