When studying automata and grammars it can feel like piling up unrelated models: DFAs, pushdown automata, Turing machines, regular grammars, context-free grammars and so on. The Chomsky hierarchy brings order to this landscape. It classifies grammars into four types according to the shape of their rules, and shows that each type matches a machine model and a class of languages. The classes are nested: each level strictly contains the one below.
Grammars in general
A general grammar has variables, terminals, a start variable and rules of the form α → β, where α and β are strings of variables and terminals and α contains at least one variable. The hierarchy arises from imposing ever stronger restrictions on the shape of these rules.
The four levels
| Type | Grammars | Rule shape | Machine model |
|---|---|---|---|
| 0 | Unrestricted | α → β | Turing machine |
| 1 | Context-sensitive | αAβ → αγβ, with γ non-empty | Linear bounded automaton |
| 2 | Context-free | A → γ | Nondeterministic pushdown automaton |
| 3 | Regular | A → aB or A → a | Finite automaton |
Type 3: regular languages
Rules have a terminal on the right, optionally followed by a single variable. A derivation looks like a path through an automaton: the current variable is the state, the terminal produced is the symbol read. Indeed regular grammars generate exactly the languages recognized by finite automata.
Example: strings over {a, b} ending in b. S → aS | bS | b.
Type 2: context-free languages
A single variable on the left, anything on the right. Nested structures can be described. The matching automaton is the pushdown automaton.
An example separating type 2 from type 3: {aⁿbⁿ : n ≥ 0}, generated by S → aSb | ε, which is not regular.
Type 1: context-sensitive languages
A variable A can be rewritten as γ only when it appears in the context α…β. An equivalent characterization requires that rules never shorten the string (|α| ≤ |β|). The matching machine is the linear bounded automaton: a nondeterministic Turing machine that may only use the space occupied by the input.
An example separating type 1 from type 2: {aⁿbⁿcⁿ : n ≥ 1}. The pumping lemma for context-free languages shows it is not type 2, while a non-contracting grammar generating it exists.
Type 0: recursively enumerable languages
No restrictions: rules may even shorten the string. Type 0 grammars generate exactly the recursively enumerable languages, those for which some Turing machine accepts exactly the strings in the language (possibly running forever on the others).
An example separating type 0 from type 1: every type 1 language is decidable, while the halting problem language is recursively enumerable but not decidable. So it belongs to type 0 and not to type 1.
A hidden level: decidable languages
The classic table has four rows, but between type 1 and type 0 there is an important class that does not correspond to a type of grammar: the decidable (or recursive) languages, for which some Turing machine always halts with a yes or no answer. We have:
regular ⊂ context-free ⊂ context-sensitive ⊂ decidable ⊂ recursively enumerable
and every inclusion is strict.
What can be decided at each level
The higher you climb, the more expressive the model and the fewer questions have an algorithmic answer.
| Problem | Type 3 | Type 2 | Type 1 | Type 0 |
|---|---|---|---|---|
| Membership of a string | Yes, linear time | Yes, polynomial time | Yes | No |
| Empty language | Yes | Yes | No | No |
| Equivalence of two descriptions | Yes | No | No | No |
Some rows deserve attention. For type 1 membership is decidable, but the problem is in general PSPACE-complete, so it can be very expensive. For type 2 emptiness is decidable (just check whether the start variable can generate some terminal string), while equivalence of two context-free grammars is undecidable.
What it is for, concretely
The hierarchy is a design tool. When defining a format or a language, choosing the lowest level that is sufficient means simpler tools and stronger guarantees:
- tokens, identifiers and numbers need only type 3, handled with finite automata;
- the nested syntax of a programming language needs type 2, handled with deterministic parsers;
- context-dependent constraints, such as "every variable must be declared before use", are usually not put in the grammar but checked in a later phase, with ordinary code.
It is a division of labour that comes straight from the theory: each level is used where it works well.
In short
- The Chomsky hierarchy classifies grammars into four types by the shape of their rules.
- Each type matches a machine: finite automaton, pushdown automaton, linear bounded automaton, Turing machine.
- The classes are strictly nested, with separating examples such as aⁿbⁿ and aⁿbⁿcⁿ.
- Between type 1 and type 0 lies the class of decidable languages.
- Moving up a level increases expressiveness and reduces the decidable questions.
