The Chomsky Hierarchy
In the Theory of Automata (TOA), the *Chomsky Hierarchy* classifies formal languages based on the complexity of the grammars that generate them and the computational models that recognize them. This hierarchy consists of four levels, each corresponding to a different type of formal grammar and automaton. Here’s a detailed breakdown of each level in the hierarchy:
1. *Type 0: Recursively Enumerable Languages*
**Formal Definition**:
*Grammar**: **Unrestricted Grammar* or **Type 0 Grammar**.
**Automaton**: **Turing Machine**.
**Characteristics**:
A language is recursively enumerable (RE) if there is a Turing machine that accepts exactly the strings in the language. The Turing machine may not halt on strings not in the language.
These languages are the most general and include all languages that can be computed or enumerated by a Turing machine.
**Unrestricted Grammar**: Production rules are of the form \( \alpha \to \beta \), where \( \alpha \) and \( \beta \) are any strings of symbols (including nonterminals and terminals), and \( \alpha \) can be empty.
**Example**:
The set of all possible strings over an alphabet is recursively enumerable.
2. *Type 1: Context-Sensitive Languages*
**Formal Definition**:
*Grammar**: **Context-Sensitive Grammar* or **Type 1 Grammar**.
**Automaton**: **Linear-Bounded Automaton (LBA)**.
**Characteristics**:
A language is context-sensitive if there is a context-sensitive grammar that generates it. Context-sensitive grammars can be used to generate languages where the production rules are of the form \( \alpha A \beta \to \alpha \gamma \beta \), where \( A \) is a nonterminal, and \( \gamma \) is a string of symbols (including possibly empty) with \( |\gamma| \geq |A| \).
Linear-bounded automata are Turing machines with tape restricted to the length of the input string. They can only use space linearly proportional to the input size.
Context-sensitive languages are more powerful than context-free languages but less powerful than recursively enumerable languages.
**Example**:
The language \( \{ a^n b^n c^n \mid n \geq 1 \} \) is context-sensitive but not context-free.
3. *Type 2: Context-Free Languages*
**Formal Definition**:
*Grammar**: **Context-Free Grammar* or **Type 2 Grammar**.
**Automaton**: **Pushdown Automaton (PDA)**.
**Characteristics**:
A language is context-free if there is a context-free grammar that generates it. Context-free grammars have production rules of the form \( A \to \alpha \), where \( A \) is a nonterminal and \( \alpha \) is a string of terminals and/or nonterminals.
Pushdown automata are finite automata with an additional stack. They can recognize context-free languages by using the stack to handle nested structures and recursion.
Context-free languages are less powerful than context-sensitive languages but more powerful than regular languages.
**Example**:
The set of balanced parentheses is a classic example of a context-free language.
4. *Type 3: Regular Languages*
**Formal Definition**:
*Grammar**: **Regular Grammar* or **Type 3 Grammar**.
**Automaton**: **Finite Automaton (FA)**.
**Characteristics**:
A language is regular if there is a regular grammar that generates it. Regular grammars have production rules of the form \( A \to aB \) or \( A \to a \), where \( A \) and \( B \) are nonterminals, and \( a \) is a terminal symbol.
Finite automata (both deterministic (DFA) and nondeterministic (NFA)) can recognize regular languages. They have a finite number of states and do not use additional memory beyond the state set.
Regular languages are the simplest in terms of computational power and are closed under operations such as union, intersection, and complement.
**Example**:
The set of all strings over the alphabet \( \{0, 1\} \) with an even number of `1`s is a regular language.
Summary of the Chomsky Hierarchy
1. **Type 0 (Recursively Enumerable Languages)**: Recognized by Turing machines. Includes all languages that can be computed by any algorithmic process.
2. **Type 1 (Context-Sensitive Languages)**: Recognized by linear-bounded automata. Includes languages that require more computational power than context-free languages but less than recursively enumerable languages.
3. **Type 2 (Context-Free Languages)**: Recognized by pushdown automata. Includes languages that are used in programming languages and many natural language constructs.
4. **Type 3 (Regular Languages)**: Recognized by finite automata. Includes the simplest languages, which can be described by regular expressions and used in lexical analysis.
Each level of the Chomsky Hierarchy provides a more powerful model of computation, and languages at higher levels of the hierarchy encompass those at lower levels. This hierarchy helps in understanding the limits of different computational models and the complexity of various formal languages.
