Over the past several chapters, you have met two different families of grammars: regular grammars, restricted to a strict right-linear or left-linear format, and context-free grammars, which relax that restriction considerably by allowing any combination of symbols on the right-hand side of a rule. A natural question follows from this progression: are there grammars even more powerful than context-free grammars, and if so, how do all of these grammar types fit together into one coherent picture?
That coherent picture is exactly what the Chomsky hierarchy provides. Introduced by linguist Noam Chomsky in the 1950s while studying the structure of natural human languages, this hierarchy organizes every grammar type into four nested categories, each one strictly more powerful than the last, with each category also corresponding to a specific computational model capable of recognizing exactly the languages that grammar type can generate.
In this tutorial, you will learn the four levels of the Chomsky hierarchy, the precise rule restrictions that define each level, the computational model associated with each grammar type, and worked examples illustrating languages that belong to each level but not the ones below it. By the end, you will have a complete map of where every grammar and automaton studied so far in this course fits.
The Chomsky hierarchy classifies grammars into four types, numbered from 3 down to 0, where a higher type number corresponds to a more restricted, less powerful grammar, and a lower type number corresponds to a more general, more powerful grammar. Each type is defined by exactly how much freedom is allowed on both sides of a production rule.
| Type | Grammar Name | Corresponding Automaton |
|---|---|---|
| Type 3 | Regular Grammar | Finite Automaton |
| Type 2 | Context-Free Grammar | Pushdown Automaton |
| Type 1 | Context-Sensitive Grammar | Linear Bounded Automaton |
| Type 0 | Unrestricted Grammar | Turing Machine |
This table is worth memorizing carefully, since it directly connects two threads running through this entire course: the grammar-based, generative view of languages, and the automaton-based, recognition view of languages. Every level of this table represents the exact same class of languages viewed from two different angles.
Type 3 grammars are exactly the regular grammars studied earlier in this course, following the strict right-linear or left-linear format. Every rule allows at most one non-terminal, positioned consistently at either the very start or the very end of the rule, alongside any number of terminal symbols.
Allowed forms (right-linear): A → aB A → a A → ε
Type 3 grammars generate exactly the class of regular languages, recognized by finite automata and describable using regular expressions, all three notations proven equivalent in earlier chapters. Languages like "strings with an even number of 1s" or "strings ending in ab" belong to this level.
Type 2 grammars are the context-free grammars covered in the previous chapter. Every rule must have exactly one non-terminal on the left-hand side, but the right-hand side can be any combination of terminals and non-terminals, with no positional restriction whatsoever.
Allowed form: A → α (where A is a single non-terminal, and α is any string of terminals and non-terminals)
This relaxed structure allows context-free grammars to describe nested and recursive patterns that Type 3 grammars cannot, such as balanced parentheses or matching counts of symbols, both demonstrated with worked examples in the previous chapter. Context-free grammars are recognized by pushdown automata, a computational model covered in the next chapter, which extends a finite automaton with a stack.
L = { 0^n 1^n | n ≥ 0 }
Type 2 grammar:
S → 0S1
S → ε
As shown in the previous two chapters, this language cannot be generated by any Type 3 regular grammar, yet it is generated effortlessly by this small Type 2 context-free grammar, illustrating exactly why Type 2 sits strictly above Type 3 in the hierarchy.
Type 1 grammars, called context-sensitive grammars, relax the restrictions even further. Instead of requiring exactly one non-terminal alone on the left-hand side of every rule, a context-sensitive rule allows the left-hand side to contain surrounding context, meaning additional symbols alongside the non-terminal being replaced, as long as the length of the right-hand side is never shorter than the length of the left-hand side.
Allowed form: αAβ → αγβ Where A is a non-terminal, α and β represent optional surrounding context (terminals and non-terminals), and γ is a non-empty string of terminals and non-terminals.
The name "context-sensitive" comes directly from this structure: the non-terminal A can only be rewritten into γ when it appears surrounded by the specific context α on its left and β on its right, meaning the same non-terminal might be rewritten differently depending on where it appears in the string. This is a sharp departure from context-free grammars, where a non-terminal can always be rewritten the same way regardless of its surroundings.
L = { 0^n 1^n 2^n | n ≥ 1 }
This language requires matching three separate counts simultaneously, one for each symbol.
No context-free grammar can generate this language, since a pushdown automaton's single stack
can reliably track and compare only one pair of counts at a time, not three simultaneously.
This example highlights exactly why context-sensitive grammars represent a genuine increase in power over context-free grammars. While a single matching count, as in 0^n 1^n, is well within reach of a context-free grammar and a pushdown automaton's stack, coordinating three separate counts to all agree with each other requires the additional expressive power that context-sensitive rules provide.
Context-sensitive languages are recognized by a linear bounded automaton, which is essentially a restricted Turing machine whose tape length is limited to a fixed multiple of the input string's length, rather than being allowed to use unlimited tape as a full Turing machine can.
Type 0 grammars, the most general and powerful level of the hierarchy, place no restriction at all on production rules beyond requiring that the left-hand side contain at least one non-terminal. The right-hand side can be any string of terminals and non-terminals, including one that is shorter than the left-hand side, unlike the length restriction required in context-sensitive grammars.
Allowed form: α → β Where α contains at least one non-terminal, and β can be any string of terminals and non-terminals, including the empty string.
Type 0 grammars correspond directly to Turing machines, the most powerful computational model studied in Theory of Computation, covered in detail in an upcoming chapter. Any language that can be generated by any grammar at all, no matter how unrestricted, can be generated by a Type 0 grammar, and correspondingly recognized by some Turing machine. This makes Type 0 the outer boundary of what any grammar-based or machine-based approach to computation can ever describe.
One of the most important properties of the Chomsky hierarchy is that these four language classes are strictly nested inside one another, forming a chain of proper subsets. Every regular language is context-free, every context-free language is context-sensitive, and every context-sensitive language falls under the unrestricted Type 0 classification.
Type 3 (Regular) ⊂ Type 2 (Context-Free) ⊂ Type 1 (Context-Sensitive) ⊂ Type 0 (Unrestricted)
Each of these containments is proper, meaning there exist languages at every level that cannot be described by any grammar at the level below it. This is exactly why the examples in this chapter were carefully chosen: "even number of 1s" belongs to Type 3, "0^n 1^n" belongs to Type 2 but not Type 3, and "0^n 1^n 2^n" belongs to Type 1 but not Type 2. Each example demonstrates a genuine increase in expressive power as you move down through the hierarchy.
| Type | Rule Restriction | Example Language | Recognizing Machine |
|---|---|---|---|
| Type 3 | One non-terminal, fixed position, at most one non-terminal per rule | Even number of 1s | Finite Automaton |
| Type 2 | Single non-terminal on left, anything on right | 0^n 1^n | Pushdown Automaton |
| Type 1 | Right-hand side length ≥ left-hand side length, context allowed | 0^n 1^n 2^n | Linear Bounded Automaton |
| Type 0 | No restrictions beyond at least one non-terminal on the left | Any recursively enumerable language | Turing Machine |
The Chomsky hierarchy is far more than a memorization exercise for exams, although it certainly does show up frequently in university coursework and competitive exams like GATE. It provides a unifying map connecting every grammar and every automaton studied throughout this entire course, showing precisely how much computational power is gained at each step, and exactly what kind of memory structure, a stack, a bounded tape, or an unlimited tape, is required to unlock that additional power.
This hierarchy also has direct practical relevance. Programming language syntax is almost always designed to stay within the context-free level, specifically because efficient parsing algorithms exist for context-free grammars, while parsing algorithms for more powerful grammar types tend to be dramatically more expensive computationally. Understanding where a language sits in this hierarchy often explains why certain parsing tools work efficiently for some tasks and struggle badly with others.
| Mistake | Correct Understanding |
|---|---|
| Assuming a lower type number means less powerful. | It is the opposite; Type 0 is the most powerful and least restricted, while Type 3 is the least powerful and most restricted. |
| Believing context-sensitive grammars allow the right-hand side to be shorter than the left-hand side. | Context-sensitive rules require the right-hand side to be at least as long as the left-hand side, unlike unrestricted Type 0 grammars. |
| Thinking every context-free language is also regular. | The containment only goes one direction; every regular language is context-free, but languages like 0^n 1^n are context-free without being regular. |
| Confusing a linear bounded automaton with a full Turing machine. | A linear bounded automaton has its tape restricted to a length proportional to the input, while a full Turing machine has unlimited tape. |
The Chomsky hierarchy ties together every grammar and automaton studied so far into a single, nested classification, ranging from the strict regular grammars of Type 3 up to the completely unrestricted grammars of Type 0. Each level corresponds precisely to a specific computational model, a finite automaton, a pushdown automaton, a linear bounded automaton, or a Turing machine, and each level strictly contains the class of languages describable by the level above it in restriction.
In this tutorial, you learned the rule restrictions defining each of the four grammar types, saw worked example languages illustrating why each level is strictly more powerful than the last, and reviewed which computational model corresponds to each level. With this complete map in place, you are ready to move on to pushdown automata, the computational model corresponding directly to the context-free grammars studied two chapters ago.