Chomsky Hierarchy

Chomsky Hierarchy — one of the most fundamental concepts in Automata Theory, originally proposed by linguist Noam Chomsky in 1956.

This hierarchy classifies formal languages (and the machines that recognize them) into four levels — from the simplest to the most powerful.

---

🧭 Overview of the Chomsky Hierarchy

Type	Grammar Type	Language Type	Automaton / Machine	Examples
Type 0	Unrestricted Grammar	Recursively Enumerable Languages	Turing Machin	{ a^n b^n c^n
Type 1	Context-Sensitive Grammar	Context-Sensitive Languages	Linear Bounded Automaton (LBA)	{ a^n b^n c^n}
Type 2	Context-Free Grammar	Context-Free Languages	Pushdown Automaton (PDA)	`{ a^n b^n}
Type 3	Regular Grammar	Regular Languages	Finite Automaton (FA)	`{ a^n}

---

🧩 1. Type 3 – Regular Languages

🔹 Grammar:

Regular Grammar has rules of the form:

• $A \rightarrow aB$
  

• $A \rightarrow a$
  

• (sometimes $A \rightarrow \epsilon$)

where $A, B$ are non-terminal symbols and $a$ is a terminal symbol.

🔹 Machine:

Recognized by a Finite Automaton (FA):

• DFA (Deterministic Finite Automaton) or NFA (Nondeterministic Finite Automaton).

• Works with a finite number of states and no external memory.

🔹 Example:

$$L = \{ a^*b^* \} = \{ \epsilon, a, ab, aab, aaab, \ldots \}$$

Grammar:

S → aS | bS | ε

🔹 Applications:

• Lexical analysis in compilers

• Pattern matching (regular expressions)

• Text search (grep, regex engines)

---

🧮 2. Type 2 – Context-Free Languages (CFLs)

🔹 Grammar:

Context-Free Grammar (CFG) has rules of the form:

$$A \rightarrow \alpha$$

where $A$ is a single non-terminal, and $\alpha$ is a string of terminals and/or non-terminals.

🔹 Machine:

Recognized by a Pushdown Automaton (PDA) —
a finite automaton with a stack (memory).

🔹 Example:

$$L = \{ a^n b^n \mid n \ge 1 \}$$

Grammar:

S → aSb | ab

🔹 Idea:

The stack is used to “remember” how many as were seen before matching bs.

🔹 Applications:

• Syntax analysis (parsing) in compilers

• Programming language grammar definitions

• Nested structures (like parentheses, HTML tags)

---

⚙️ 3. Type 1 – Context-Sensitive Languages (CSLs)

🔹 Grammar:

Context-Sensitive Grammar (CSG) has rules of the form:

$$\alpha A \beta \rightarrow \alpha \gamma \beta$$

where:

• $A$ is a non-terminal,

• $\alpha, \beta, \gamma$are strings of terminals/non-terminals,

• and $|\gamma| \ge 1$ (the rule cannot make the string shorter).

So the replacement of $A$ may depend on its context (the symbols around it).

🔹 Machine:

Recognized by a Linear Bounded Automaton (LBA) —
a Turing Machine whose tape is bounded by the input length (it cannot use infinite tape space).

🔹 Example:

$$L = \{ a^n b^n c^n \mid n \ge 1 \}$$

Grammar sketch:

S → aSBC | abc
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc

🔹 Applications:

• Natural language processing (some human languages are context-sensitive)

• Theoretical study of resource-bounded computation

---

🧠 4. Type 0 – Recursively Enumerable Languages

🔹 Grammar:

Unrestricted Grammar —
rules can be of the general form:

$$\alpha \rightarrow \beta$$

where $\alpha, \beta$ are strings of terminals and non-terminals,
and $\alpha$ contains at least one non-terminal.

There are no restrictions on how rewriting happens.

🔹 Machine:

Recognized by a Turing Machine (TM).
This is the most general and most powerful computational model.

🔹 Example:

Languages that can be recognized by a Turing machine, e.g.:

$$L = \{ a^i b^j c^k \mid i \times j = k \}$$

This cannot be handled by simpler automata.

🔹 Applications:

• All computable problems

• Defines the boundary of what can be computed algorithmically

---

⚖️ Hierarchy Relationships

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

That means:

• Every regular language is also context-free.

• Every context-free language is also context-sensitive.

• Every context-sensitive language is also recursively enumerable.

But the reverse is not true.

Think of the hierarchy as a ladder of computational power:

Regular  <  Context-Free  <  Context-Sensitive  <  Recursively Enumerable
   (FA)          (PDA)             (LBA)                 (TM)

As we move up the hierarchy:

• The grammar rules become more general.

• The automaton becomes more powerful.

• The languages become more complex.

We have also met several other language families that can be fitted into this picture. Including the families of deterministic context-free languages(LDCF) and recursive languages (LREC), we arrive at the extended hierarchy shown in the following figure.