The Chomsky Hierarchy

Classification of Formal Grammars

The Chomsky hierarchy, introduced by Noam Chomsky in 1956, classifies formal grammars into four types based on their generative power. This classification creates a containment hierarchy where each grammar type generates a corresponding class of formal languages.

Formal Grammars

A formal grammar $G$ is defined as a 4-tuple:

$G = (V, \Sigma, R, S)$

Where:

• $V$ is a finite set of non-terminal symbols
• $\Sigma$ is a finite set of terminal symbols (the alphabet), where $V \cap \Sigma = \emptyset$
• $R$ is a finite set of production rules of the form $\alpha \rightarrow \beta$
• $S \in V$ is the start symbol

The Four Types of Grammars

Type-0: Unrestricted Grammars

• Production rule form: $\alpha \rightarrow \beta$ where $\alpha$ contains at least one non-terminal
• Language class: Recursively enumerable languages
• Computational model: Turing machine
• Constraints: None except that the left-hand side must contain at least one non-terminal

Example production: $aAb \rightarrow aaBb$

Type-1: Context-Sensitive Grammars

• Production rule form: $\alpha A \beta \rightarrow \alpha \gamma \beta$ where $|\gamma| \geq 1$
• Language class: Context-sensitive languages
• Computational model: Linear-bounded automaton
• Constraints: The length of the right-hand side must be greater than or equal to the length of the left-hand side

Example production: $aAb \rightarrow aabb$

Type-2: Context-Free Grammars

• Production rule form: $A \rightarrow \gamma$ where $A$ is a single non-terminal
• Language class: Context-free languages
• Computational model: Pushdown automaton
• Constraints: The left-hand side must be a single non-terminal

Example production: $A \rightarrow aAb \mid ab$

Type-3: Regular Grammars

• Production rule form: $A \rightarrow aB \mid a$ where $A, B$ are non-terminals and $a$ is a terminal
• Language class: Regular languages
• Computational model: Finite-state automaton
• Constraints: The right-hand side must be either a single terminal or a terminal followed by a single non-terminal

Example production: $A \rightarrow aB \mid a$

Hierarchy Visualization

Mathematical Relationships

$\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursively Enumerable}$

Chomsky Normal Form (CNF)

For context-free grammars, the Chomsky Normal Form is a special form where all productions are of the form:

1. $A \rightarrow BC$ (a non-terminal produces exactly two non-terminals)
2. $A \rightarrow a$ (a non-terminal produces a terminal)
3. $S \rightarrow \varepsilon$ (only if $S$ doesn't appear on the right-hand side of any production)

Where $A, B, C$ are non-terminals, $a$ is a terminal, and $S$ is the start symbol.

Every context-free grammar can be transformed into an equivalent grammar in Chomsky Normal Form.

Computational Power and Decidability

Type-0 (Recursively Enumerable)

• Decidability: The membership problem is undecidable
• Example problem: The halting problem

Type-1 (Context-Sensitive)

• Decidability: The membership problem is decidable but PSPACE-complete
• Example problem: Linear bounded automaton acceptance

Type-2 (Context-Free)

• Decidability: The membership problem is decidable in polynomial time
• Example problem: Recognition of programming language syntax

Type-3 (Regular)

• Decidability: The membership problem is decidable in linear time
• Example problem: Pattern matching with regular expressions

Applications in Computer Science

1. Type-3 (Regular):

   • Lexical analysis in compilers
   • Pattern matching
   • Protocol specification

2. Type-2 (Context-Free):

   • Syntax of programming languages
   • Parsing in compilers
   • XML and HTML document validation

3. Type-1 (Context-Sensitive):

   • Natural language processing
   • Some programming language features (e.g., declarations before use)

4. Type-0 (Unrestricted):

   • Theoretical computation models
   • Universal computation

Theoretical Significance

The Chomsky hierarchy provides a framework for understanding:

1. The expressive power of different formal systems
2. The computational complexity of language recognition
3. The trade-off between expressiveness and decidability
4. The relationship between formal languages and automata

In the next section, we'll explore context-free grammars in greater depth, as they are particularly important in programming language design and compiler construction.