Symptom
The most upvoted answer in Stack Overflow history is a refusal to answer. Someone asked how to match nested HTML tags with a regular expression, and the reply is a page of escalating horror about the centre not holding. It is funny, and it is also a theorem, which is not obvious from reading it.
The practical version of the symptom is quieter and more expensive. Someone
writes a regex to strip HTML tags, and it works on the test cases. Then a
comment contains a <, or an attribute value contains >, or tags nest three
deep, and the regex silently produces wrong output rather than failing. The fix
is another regex, with a lookahead. Six months later the sanitizer has fourteen
alternations, a security advisory, and nobody willing to touch it.
The same shape recurs: parsing JSON with string splitting, validating balanced parentheses in a config file with pattern matching, extracting nested function calls from source with a scanner. In each case the tool cannot express the property, so the code accumulates special cases forever and asymptotically approaches a parser that nobody designed.
Statement
Grammars, and the languages they generate, fall into four strictly nested classes, each corresponding exactly to a class of machine:
| Type | Grammar | Machine | Production form |
|---|---|---|---|
| 3 | Regular | Finite automaton | $A \to aB$ or $A \to a$ |
| 2 | Context-free | Pushdown automaton | $A \to \gamma$ |
| 1 | Context-sensitive | Linear-bounded automaton | $\alpha A \beta \to \alpha\gamma\beta$ |
| 0 | Unrestricted | Turing machine | $\alpha \to \beta$ |
The containment is strict at every level:
$$\text{Regular} \subsetneq \text{Context-free} \subsetneq \text{Context-sensitive} \subsetneq \text{Recursively enumerable}$$The engineering content is in the strictness. Each inclusion being proper means there is a concrete language you cannot recognize with the weaker machine, no matter how clever you are. $a^n b^n$ separates regular from context-free. $a^n b^n c^n$ separates context-free from context-sensitive. The halting language separates decidable from recursively enumerable.
And the correspondence between grammar shape and machine is not an analogy. It is an exact equivalence, proved by mutual simulation, which is why the shape of your grammar rules tells you what memory your parser will need.
Argument
Why the machines line up with the grammar forms. The key quantity is memory discipline. A finite automaton has a fixed number of states — a bounded amount of memory — and regular productions $A \to aB$ are exactly rules that carry no information forward beyond a single symbol of state. A pushdown automaton adds a stack, and context-free productions $A \to \gamma$ are exactly what a stack can track, because expanding a nonterminal into a string of symbols to be processed later is pushing. A linear-bounded automaton has a tape proportional to the input, matching non-contracting productions, which can never make the working string shorter than the input. Remove the restriction and you have unbounded tape and a Turing machine (T013).
So the hierarchy is really a hierarchy of memory: none, a stack, a linear amount, unbounded. Everything else follows.
Why regex cannot match nested tags. The pumping lemma for regular languages says: for any regular language there is a length $p$ such that every string of length at least $p$ splits as $xyz$ with $|xy| \le p$, $|y| \ge 1$, and $xy^iz$ in the language for all $i \ge 0$. The reason is pigeonhole (T001): a DFA with $p$ states reading a string of length $\ge p$ must revisit a state, and the loop between the two visits can be repeated any number of times without the machine noticing.
Apply it to ${a^nb^n}$. Given $p$, take $a^pb^p$. Since $|xy| \le p$, $y$ is all $a$s, so pumping to $xy^2z$ adds $a$s without $b$s, giving a string not in the language. Contradiction. There is no regular language of balanced things, and nested HTML tags are exactly that. No regex — in the formal sense — will ever match them, however long.
Myhill–Nerode (T040) is the sharper tool: $a^nb^n$ has infinitely many distinguishable prefixes, since $a^i$ and $a^j$ with $i \ne j$ are distinguished by $b^i$. Infinitely many equivalence classes, no finite automaton, no argument about pumping needed.
Why context-free is where programming languages sit. Nested constructs — parentheses, blocks, expressions — are exactly what a stack handles, and the correspondence is literal: the recursive descent parser’s call stack is the pushdown automaton’s stack. A grammar that is LL(k) or LR(k) admits a deterministic linear-time parser, which is why real compilers use those subclasses rather than the full class.
Why languages are not purely context-free either. “Every variable must be
declared before use” needs unbounded correlation between distant parts of the
string, which is the $a^nb^nc^n$ shape. This is why every compiler has a
semantic analysis phase after parsing: the type checker is doing the
context-sensitive part, and no amount of grammar work will absorb it. C is worse
still — x * y; is a declaration or a multiplication depending on whether x
is a typedef, so the grammar is genuinely ambiguous without symbol-table
feedback, and that is the notorious “lexer hack.”
Forbids
Matching balanced or nested structures with a regular expression. HTML, XML, JSON, S-expressions, nested comments, and balanced parentheses are all context-free and not regular. This is not a limitation of a library, and no feature request fixes it.
A finite automaton counting without a bound. Anything requiring “the same
number of X as Y” with unbounded counts is out. This is why you cannot validate
that a config has matching begin/end markers with a lexer alone.
A pushdown automaton enforcing cross-references. Declare-before-use, type agreement, and matching function arity to call sites are context-sensitive. Attempting them in the grammar produces exponential rule blowup and still fails.
A single unified “just parse it” phase. The hierarchy is why compilers have stages. Each stage handles the level its machine can express, and the structure of the toolchain is a consequence of the theorem, not a convention.
Does not forbid
Modern “regex” engines are not regular, and this trips people constantly.
PCRE, Perl, Python’s re, and Java’s regex all have backreferences and
recursion. Backreferences alone push you past context-free — (a+)b\1 is not
even context-free — and PCRE’s recursive patterns (?R) genuinely can match
balanced parentheses. So “you can’t match HTML with a regex” is true of formal
regular expressions and false of PCRE, which can do it badly. The reason not
to is now practical: backtracking engines on these patterns hit exponential
blowup, which is the ReDoS vulnerability class. RE2 and Go’s regexp deliberately
omit backreferences to stay regular and guarantee linear time, which is the
same trade as T012’s total languages.
Bounded nesting is regular. “Match tags nested at most three deep” is a finite condition and a perfectly good regex, if an ugly one. Many real problems have a bound, and if yours does, the theorem does not apply to you. The failure mode is assuming a bound that the input does not respect.
Context-free parsers handle plenty of context-sensitive-looking things via side channels. Symbol tables, attribute grammars, and two-pass compilation are all ways to do the context-sensitive work outside the grammar. The theorem says the grammar cannot express it, not that your program cannot check it.
The hierarchy is not the only classification, and modern parsing lives between the levels. Parsing expression grammars (PEGs) are incomparable with context-free: they handle some non-context-free languages, and their ordered choice makes them unambiguous by construction, but they cannot express some context-free languages. Tree-adjoining grammars and other mildly context-sensitive formalisms sit strictly between types 2 and 1, and are what computational linguistics actually uses.
Practical parsers are not restricted to LL/LR. GLR (used by tree-sitter and
Bison’s %glr-parser) handles all context-free grammars including ambiguous
ones, in cubic worst case and near-linear practice; Earley parsing does the same.
“Not LR(1)” is a statement about a parser-generator algorithm, not about the
hierarchy.
Boundary
- Closure properties are the practical tool. Regular languages are closed under union, intersection, and complement; context-free languages are closed under union but not intersection or complement. That is why you can compose lexer rules freely and cannot intersect two grammars, and it explains a lot of parser-generator behaviour.
- Decidability degrades as you climb. Equivalence of two DFAs is decidable in polynomial time; equivalence of two context-free grammars is undecidable, as is ambiguity. Every step up the ladder buys expressiveness and pays in analyzability, which is the same trade as T012.
- Complexity, not just computability. Regular is $O(n)$ with $O(1)$ memory. Context-free is $O(n^3)$ in general (CYK, Earley), $O(n)$ for LL/LR. Context-sensitive recognition is PSPACE-complete. The ladder is a cost curve.
- The security reading. LANGSEC argues that most injection vulnerabilities come from recognizing input with a machine weaker than the language actually requires — ad-hoc parsers for context-free formats. “Full recognition before processing” is the discipline the hierarchy implies.
- Two formalisms, one power, repeatedly. Kleene’s theorem (T039) shows regular expressions and finite automata are the same class; Codd’s theorem (T069) does the same for relational algebra and calculus. This coincidence is common enough to be a genre.