A machine with finitely many states, one symbol at a time, no memory but where it stands. Kleene proved what such a machine can recognize is exactly the class of regular languages — and that every regular language has a regular expression. Down the center, data flows: a string goes in, the machine steps state-by-state, accept or reject comes out. The blue team builds the machine and proves it; the red team attacks the frame and flips a state to break it.
source S. C. Kleene, Representation of Events in Nerve Nets and Finite Automata (RAND RM-704, 1951), in Automata Studies, Shannon & McCarthy eds., Princeton, 1956 — archive.org/details/automatastudies0000vari (the containing volume; Kleene pp. 3–42). Rendered, not quoted.
A deterministic finite automaton is a 5-tuple: an alphabet Σ={0,1}, a finite set of states, one start state, a set of accepting states, and a total transition function δ(state, symbol)→state. Feed a string left to right; on each symbol the machine jumps once. Accept iff the state where the input runs out is an accepting state. No stack, no counter — the current state is the entire memory.
Live transition table of the machine on the panel — the highlighted cell is where it stands now:
McCulloch & Pitts (1943) wired idealized neurons into nerve nets — all-or-none units firing in discrete ticks. Kleene asked the next sphere's question: what events can such a net respond to? His answer names the regular events and gives the regular expression to write each one down.
That algebra of union, concatenation and star is the same syntax your editor runs when you type a search pattern. Each sphere is the next one's premise: neuron → finite automaton → regex in every editor.
The blue team's live check: for both machines, run every string of length 0–8 (511 strings) and compare the machine's verdict to an independent brute-force oracle. Zero disagreements = the DFA recognizes exactly its language. If red flips a state, a mismatch appears here and the badge goes red.
Two things go in: a preset language and an input string over Σ={0,1}. Pick one of two regular languages, each a real DFA:
| preset | accepts exactly | states |
|---|---|---|
| even 1s | strings with an even number of 1s | 2 |
| contains 101 | strings with 101 somewhere inside | 4 |
Type any string of 0s and 1s below (other characters are dropped). The machine reads it head-first; that is what you feed the panel.
The accept/reject verdict is computed by walking δ live — never looked up. Step through, or run to the end.
What the machine produces, proven: for each preset the DFA accepts a string iff the string is in the language — verified against a brute-force oracle over all 511 strings of length 0–8, with zero disagreements. Kleene's theorem then guarantees an equivalent regular expression, shown above for the current preset.
The blue team's witness (left) re-runs the whole 0–8 sweep live; the red team (right) tries to make it lie.
Balanced parentheses, palindromes, arithmetic with nesting — all outside the regular languages. The finite automaton is the floor of the Chomsky hierarchy, not its ceiling; a pushdown automaton (a stack) climbs the next rung. Kleene's machine is where computation starts, not where it ends.
"Regex engines recognize the regular languages." Cut. Perl/PCRE-style regex with backreferences (e.g. (.*)\1) matches non-regular languages and can run in exponential time. Kleene's regular expressions are strictly weaker — and always linear.
"Kleene invented the finite automaton." Cut. He formalized the regular events of the McCulloch–Pitts net (1943); the crisp DFA/NFA framing and the subset construction are Rabin & Scott (1959). Credited, not pretended.
"The minimal machine for a language is unique." Kept, corrected. True for the minimal DFA — unique up to renaming, by Myhill–Nerode. False for NFAs, which can have several non-isomorphic minima.
The red team's move: flip one state from non-accepting to accepting in both machines — a single bit in the accepting set. Some strings are now misclassified against the oracle. The witness (window 7) is watching.
Flip one accepting bit and the machine accepts strings it must reject — the witness re-runs the 0–8 sweep, finds disagreements with the oracle, and turns red. Nothing is faked; the void is real and it is caught.