The Chomsky hierarchy — four tiers of automata
Parent: logic
Chomsky (1956), the linguist, classified formal grammars into four nested types; each matches a class of automaton (by how much memory it has) and a class of language. The Turing machine is the outermost tier.
| Type | Grammar | Automaton | Memory | Languages | e.g. |
|---|---|---|---|---|---|
| 3 | regular | finite automaton (DFA/NFA) | none | regular | a*b* |
| 2 | context-free | pushdown automaton (one stack) | a stack | context-free | aⁿbⁿ, balanced parens, most syntax |
| 1 | context-sensitive | linear-bounded automaton (tape ≤ input) | bounded tape | context-sensitive | aⁿbⁿcⁿ |
| 0 | unrestricted | Turing machine | unbounded tape | recursively enumerable | anything computable |
Strict inclusions: regular ⊊ context-free ⊊ context-sensitive ⊊ recursively enumerable.
The ladder is really about memory
- none → a finite automaton can only be in one of finitely many states; it can't count, so it fails
aⁿbⁿ. - one stack → nesting/recursion (balanced brackets), but only last-in-first-out; fails
aⁿbⁿcⁿ(needs two counts). - bounded tape → context-sensitive; still decidable (finite configurations).
- unbounded tape → full computation. Turing (Type 0) is the top because unbounded memory = universal computation.
Where undecidability enters
The jump from Type 1 (decidable) to Type 0 (only semi-decidable) is exactly the phase transition: membership in a context-sensitive language is decidable, but membership in an r.e. language is only recognizable — deciding it is the halting problem (history). Unbounded memory buys universality and undecidability in one step.
Linguistics motivation
Chomsky's point was about natural language: finite-state (Type 3) grammars can't capture nested clause structure, so language needs at least context-free; and phenomena like cross-serial dependencies push it to mildly context-sensitive. The hierarchy was born to say "human syntax is not regular."
Full story of why a linguist built this → history.
Each tier (children)
- regular-languages — Type 3: finite automata = regex, no memory.
- context-free-languages — Type 2: one stack, nesting.
- context-sensitive-languages — Type 1: bounded tape, still decidable.
- recursively-enumerable-languages — Type 0: Turing machines, where undecidability begins.