The Chomsky Hierarchy

The Chomsky Hierarchy

The Chomsky hierarchy classifies formal languages into four types based on their generative power. These types are: regular languages, context-free languages, context-sensitive languages, and recursively enumerable languages. Each type of language corresponds to a class of automaton or grammar that can generate or recognize the language.

Types of Languages

1. Regular Languages

Regular languages are the simplest type in the Chomsky hierarchy. They can be described by regular expressions and recognized by finite automata. A regular language can be defined using a finite set of rules or transitions. For example, the language of all strings over the alphabet {a, b} that contain an even number of a's can be expressed as a regular expression: (b*ab*a)*.

2. Context-Free Languages

Context-free languages (CFLs) are generated by context-free grammars (CFGs). A CFG consists of a set of production rules that describe how to form strings from the language's alphabet. CFLs are more powerful than regular languages and can represent languages that require a form of nesting or recursion. An example of a context-free language is the set of balanced parentheses, which can be generated by the grammar:

S -> SS | (S) | ε

Here, S is a non-terminal symbol that can be replaced with either two instances of S, a pair of parentheses containing S, or an empty string (ε).

3. Context-Sensitive Languages

Context-sensitive languages (CSLs) are generated by context-sensitive grammars. These grammars are more powerful than context-free grammars and can express languages that require context to determine how to apply production rules. An example of a context-sensitive language is the language {a^n b^n c^n | n ≥ 1}, which requires an equal number of a's, b's, and c's. This language cannot be generated by a context-free grammar.

4. Recursively Enumerable Languages

Recursively enumerable languages (RELs) are the most general class in the Chomsky hierarchy. They can be recognized by Turing machines. A language is recursively enumerable if there exists a Turing machine that will accept any string in the language but may not halt for strings not in the language. An example of a recursively enumerable language is the set of all Turing machine descriptions that halt on empty input.

Relationships Among Language Classes

The Chomsky hierarchy shows a clear relationship among the different classes of languages:

• Every regular language is also a context-free language.
• Every context-free language is also a context-sensitive language.
• Every context-sensitive language is also a recursively enumerable language.

However, the reverse is not true. There are languages that are context-free but not regular, context-sensitive but not context-free, and recursively enumerable but not recursive.

The Language ALAN

ALAN is a specific language defined as the set of all code words that do not represent Turing machines that accept them. This language is important in demonstrating the limitations of Turing machines. The proof that ALAN is not recursively enumerable involves a contradiction based on the properties of Turing machines.

Suppose ALAN is recursively enumerable. This means there exists a Turing machine T that accepts all words in ALAN. Let code(T) denote the code word for T. We must ask whether code(T) is in ALAN.

Case 1: code(T) is in ALAN

1. By definition, T accepts ALAN.
2. ALAN contains no code word that is accepted by the machine it represents.
3. code(T) is in ALAN.
4. T accepts the word code(T).
5. code(T) is not in ALAN.
6. This leads to a contradiction.

Case 2: code(T) is not in ALAN

1. T accepts ALAN.
2. If a word is not accepted by the machine it represents, it is in ALAN.
3. code(T) is not in ALAN.
4. code(T) is not accepted by T.
5. code(T) is in ALAN.
6. This leads to a contradiction.

Since both cases lead to contradictions, ALAN cannot be recursively enumerable.

Conclusion

The Chomsky hierarchy provides a framework for understanding the different classes of formal languages and their relationships. It highlights the limitations of Turing machines and the concept of decidability in computation. Understanding this hierarchy is essential for studying theoretical computer science.

• Regular languages are recognized by finite automata.
• Context-free languages are recognized by pushdown automata.
• Context-sensitive languages are recognized by linear-bounded automata.
• Recursively enumerable languages are recognized by Turing machines.

Check your understanding

1. What type of automaton recognizes context-free languages?
2. Provide an example of a context-sensitive language.
3. Explain why ALAN is not recursively enumerable.
4. What is the relationship between regular languages and context-free languages?