A finite automaton has no memory of how deep it is, so it cannot match anbn or count nested brackets. A context-free grammar can: its stack of pending non-terminals is the counter. This instrument runs two real CFGs, decides membership with a live recognizer, and shows the leftmost derivation for every string it accepts. Rendered, not quoted.
Source: Chomsky, Three Models for the Description of Language (1956) & Syntactic Structures (1957), where the grammar hierarchy is set out. source archive.org/details/NoamChomskySyntcaticStructures — full public-domain text.
A CFG is a 4-tuple (N, Σ, P, S): non-terminals, terminals, productions, and a start symbol. Every production has a single non-terminal on its left — that is what makes it context-free.
anbn: S → a S b | ε
balanced ( ): S → ( S ) S | ε
The recognizer is a genuine parser: derive(A,i,j) asks "can non-terminal A span s[i..j)?", splitting each production's symbols across the substring — a memoized CYK-style chart, not a regex.
One rung below on the Chomsky hierarchy sits the-finite-automaton (regular languages). A DFA has finitely many states and no stack, so a pumping argument proves it cannot recognize anbn — it loses count.
This sphere is the rung above: the pushdown stack of pending S's remembers exactly how many a's are still owed a matching b. Next rung up: context-sensitive grammars (anbncn), which a CFG in turn cannot reach.
Live re-check, independent of boot. It recognizes aaabbb (must accept), aabbb (must reject), and (()) (must accept) against the current grammar and compares to the known truth.
If window 6 tampers the grammar, an expected-accept turns to reject, the comparison fails, and this badge flips red.
Pick a grammar, type a string over its alphabet. anbn reads a/b; parens reads (/). Max 24 symbols.
The verdict is computed live by the recognizer and cross-checked against an independent oracle (regex for aⁿbⁿ, a stack counter for parens). They must agree.
Proven: the recognizer agrees with the oracle on all 511 strings over {a,b} of length ≤8 and all 511 strings over {(,)} of length ≤8; anbn is accepted for n=0..8 while anbn+1 and an+1bn are rejected.
The honest case against over-claiming:
Retracted while building this:
"S → S a S b handles the same language and is cleaner."
→ Rejected: that grammar is left-recursive and ambiguous, and it accepts strings like abab that are not in anbn. Kept the clean S → a S b | ε.
"A regex a*b* is close enough."
→ False: a*b* accepts aab. No regular language equals anbn — that is exactly the point.
The disclosed planted void. This is real and it is caught. It drops the base case S → ε from the live grammar, so no derivation can ever terminate and valid strings get rejected.
boot's selfcheck() also plants this void internally, asserts aabb now fails, then restores — proving the void makes noise before you ever click.