The Chomsky Hierarchy
Four nested classes of language, and exactly what memory each one costs you.
Skip to the animationThe Chomsky hierarchy sorts every formal language into four nested classes, each one recognised by a strictly more powerful kind of machine than the last.
Four classes, each inside the next
The hierarchy is a containment, not a list. Every regular language is context-free; every context-free language is context-sensitive; every context-sensitive language is recursively enumerable. Each step outward adds languages you could not describe before, and demands a machine with more memory to recognise them.
| Type | Class | Machine | Memory it has | Example |
|---|---|---|---|---|
| 3 | Regular | Finite automaton | finite, fixed | (ab)* |
| 2 | Context-free | Pushdown automaton | one unbounded stack | aⁿbⁿ |
| 1 | Context-sensitive | Linear bounded automaton | tape the size of the input | aⁿbⁿcⁿ |
| 0 | Recursively enumerable | Turing machine | unbounded tape | the halting problem |
The containments are strict. aⁿbⁿ really is context-free and really is not regular, so no amount of cleverness will produce a DFA for it.
What each extra piece of memory buys
- Finite states only. You can remember a bounded amount — the last symbol, a position in a fixed pattern — but you cannot count without limit.
- A stack. Now you can match nested things: push on the way in, pop on the way out. This is why
aⁿbⁿ, balanced brackets and programming-language syntax are all context-free. - A read-write tape bounded by the input. Three-way counting becomes possible.
aⁿbⁿcⁿis not context-free because checking thebs against theas pops the stack you needed for thecs. - An unbounded tape. Everything computable, at the price that the machine may loop forever.
Recognisable is not the same as decidable
At Type 0 a distinction opens up that does not exist further in. A language is decidable if some machine always halts with the right yes/no answer; it is merely recognisable if a machine halts and says yes on members, but may run forever on non-members.
The halting problem is the standard example of the gap: recognisable, not decidable. Types 1 through 3 are all decidable, so this is genuinely the outermost ring's problem alone.
Why anyone builds weak machines on purpose
Since Turing machines can do everything, it is fair to ask why the inner rings matter. The answer is that weakness is a feature — the less a class can express, the more you can prove and optimise:
- Regular languages are closed under union, intersection and complement, have a unique minimal DFA, and match in one pass with constant memory. Hence regular expressions for tokens.
- Context-free grammars can be parsed in cubic time in general, and linear time for the practical subsets — hence LL and LR parsers for syntax.
- Nothing useful is decidable about arbitrary Turing machines, which is why no compiler will tell you whether your program terminates.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.