The Chomsky Hierarchy: Classifying Formal Languages

The Four Tiers of Grammar

The Chomsky Hierarchy, developed by linguist Noam Chomsky, categorizes formal grammars into four types based on the restrictiveness of their production rules. More restrictive rules lead to simpler grammars that generate smaller classes of languages, which in turn can be recognized by less powerful automata.

To get a concise overview of these four levels, please watch the following video. It breaks down each grammar type, its production rule format, the language class it generates, and its corresponding machine model.

To summarize and consolidate what you've just seen, here is a table that lays out the hierarchy from the most restrictive (Type 3) to the least restrictive (Type 0).

Note: In the table, $A,B$ are variables, $a$ is a terminal, and $\alpha ,\beta$ are strings of variables and terminals.

A Hierarchy of Nested Sets

The term "hierarchy" is used because these language classes are properly nested within each other. This means that every regular language is also context-free, every context-free language is also context-sensitive, and so on. The "proper" part of this containment means that there are languages at each level that do not belong to the level below it.

This creates a beautiful, layered structure of computational power.

Let's prove this proper containment by looking at some familiar examples.

1. Regular ⊂ Context-Free
   A language is regular if it can be described by a finite automaton, which has no memory. A language is context-free if it can be recognized by a pushdown automaton, which has a stack for memory.
   The classic example separating these two is $L=\{a^n{b}^n\mid n\ge 0\}$.

   • It is Context-Free: We can design a PDA that pushes an a onto the stack for every a it reads, and then pops an a for every b it reads. The string is accepted if the stack is empty at the end.
   • It is Not Regular: As you know from Module 4, the Pumping Lemma for regular languages can be used to prove that a finite automaton (with its finite memory) cannot keep count of an arbitrary number of a's to match them with b's.

2. Context-Free ⊂ Context-Sensitive
   A language is context-sensitive if it's recognized by a Linear Bounded Automaton, whose memory (tape) is proportional to the input length.
   The canonical example here is $L=\{a^n{b}^n{c}^n\mid n\ge 0\}$.

   • It is Context-Sensitive: We saw in the last lesson on Turing Machines that this language can be accepted by a TM. Since that TM only needs to scan back and forth across the input, its tape usage is linear in the input size, making it recognizable by an LBA.
   • It is Not Context-Free: As covered in Module 7, the Pumping Lemma for CFLs can prove that a single stack is insufficient to enforce the three-way count between a's, b's, and c's.

The Full Picture: Recursive and Recursively Enumerable Languages

The hierarchy extends beyond what grammars alone can cleanly define. The world of Turing Machines gives us two more important classes.

• Recursive (or Decidable) Languages: A language is recursive if there is a Turing Machine that accepts all strings in the language and rejects all strings not in the language. Crucially, this TM is guaranteed to halt on every input.
• Recursively Enumerable (RE) Languages: A language is RE if there is a Turing Machine that accepts all strings in the language. However, for strings not in the language, the TM might reject or it might loop forever.

With these definitions, we can complete the hierarchy.

3. Context-Sensitive ⊂ Recursive
   Every context-sensitive language is recursive. An LBA has a finite number of states and its tape is bounded. This means there's a finite (though very large) number of unique configurations it can be in. If an LBA were to run forever on an input, it must eventually repeat a configuration, entering a loop. We can detect this, so an LBA can always be made to halt.
   But is there a recursive language that is not context-sensitive? Yes. An example is the language of valid LBA computations that accept. Proving this is advanced, but intuitively, it requires simulating another machine, which can require more than linear space.

4. Recursive ⊂ Recursively Enumerable
   Every recursive language is, by definition, also recursively enumerable. The TM that decides the language also recognizes it.
   The most famous example of a language that is RE but not recursive is the Halting Problem ($A_{TM}$).

   • It is Recursively Enumerable: A Universal Turing Machine can simulate any TM $M$ on an input $w$. If $M$ halts, the UTM accepts. Thus, $A_{TM}$ is recognized.
   • It is Not Recursive: As we will prove formally in the next module, there is no Turing Machine that can decide for all pairs $(M,w)$ whether $M$ will halt on $w$.

The following reading summarizes this entire structure and highlights the languages that separate each level.

Conclusion

Today, we have assembled the puzzle pieces from our previous lessons into a coherent whole: the Chomsky Hierarchy. This framework is a cornerstone of theoretical computer science, providing a powerful lens through which to understand computation, language, and complexity.

Key Takeaways:

• The Chomsky Hierarchy classifies grammars, languages, and automata into four main types (0, 1, 2, 3).
• The hierarchy is based on restrictions on grammar rules: the more restrictions, the less powerful the language class.
• The language classes exhibit proper containment: Regular ⊂ Context-Free ⊂ Context-Sensitive ⊂ Recursive ⊂ Recursively Enumerable.
• This containment is proven by "separating languages" like $\{a^n{b}^n\}$, $\{a^n{b}^n{c}^n\}$, and the Halting Problem, which exist at one level but not the one below.
• This hierarchy essentially maps out what is possible with different levels of computational resources (no memory, a stack, linear memory, and unrestricted memory).

Preview of the Next Lesson:
We have reached the outermost ring of our diagram: the Recursively Enumerable languages. A natural question arises: is there anything outside that ring? The answer is yes. In our next lesson, we will use a powerful proof technique called diagonalization to show that there are languages that are not even recursively enumerable—problems that no Turing Machine can even begin to solve. This will lead us directly into the formal proof of the undecidability of the Halting Problem.