Answer

Chomsky Hierarchy (Noam Chomsky, 1956) classifies formal grammars and their languages by production rule restrictions into 4 types, forming a strict containment hierarchy.

---

Hierarchy Overview

Type	Name	Production Form	Language Class	Recognizing Automaton
Type-0	Unrestricted	$\alpha \rightarrow \beta$, $\alpha,\beta \in (V\cup T)^*$, $\alpha
eq \epsilon$	Recursively Enumerable (RE)	Turing Machine (TM)
Type-1	Context-Sensitive	$|\alpha| \le |\beta|$, $\alpha \rightarrow \beta$ with context	Context-Sensitive (CSL)	Linear Bounded Automaton (LBA)
Type-2	Context-Free	$A \rightarrow \gamma$, $A \in V$, $\gamma \in (V\cup T)^*$	Context-Free (CFL)	Pushdown Automaton (PDA)
Type-3	Regular	$A \rightarrow aB \mid a$ (right-linear) or $A \rightarrow Ba \mid a$ (left-linear)	Regular (REG)	Finite Automaton (DFA/NFA)

Containment:
$$\text{REG} \subset \text{DCFL} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} \subset \text{ALL}$$
Each is a proper subset of the next.

---

Detailed Explanation with Examples

Type-3: Regular Languages

• Grammar: Right-linear ($A \rightarrow aB \mid a$) or Left-linear.
• Automaton: DFA/NFA/$\epsilon$-NFA (equivalent power).
• Properties: Closed under union, intersection, complement, concatenation, star. Membership in $O(n)$.
• Example 1: $L = \{a^m b^n \mid m,n \ge 0\}$
  • Grammar: $S \rightarrow aS \mid bA \mid \epsilon$, $A \rightarrow bA \mid \epsilon$
• Example 2: Binary strings with even number of 1's: $(0^*10^*1)^*0^*$
  • DFA: 2 states tracking parity

Type-2: Context-Free Languages (CFL)

• Grammar: $A \rightarrow \gamma$ (single non-terminal LHS).
• Automaton: PDA (NPDA > DPDA in power).
• Properties: Closed under union, concat, star. Not closed under intersection, complement. Parsing $O(n^3)$ (CYK).
• Example 1: $L = \{a^n b^n \mid n \ge 0\}$ (matching counts)
  • Grammar: $S \rightarrow aSb \mid \epsilon$
  • PDA: push $a$'s, pop for $b$'s
• Example 2: Balanced parentheses
  • Grammar: $S \rightarrow (S) \mid SS \mid \epsilon$
• Example 3: $\{ww^R \mid w \in \{a,b\}^*\}$ (palindromes)
  • NPDA guesses middle

Type-1: Context-Sensitive Languages (CSL)

• Grammar: $|\alpha| \le |\beta|$, productions like $\alpha A \beta \rightarrow \alpha \gamma \beta$ (context around $A$).
• Automaton: LBA = TM with tape bounded by $k|w|$.
• Properties: Membership decidable (PSPACE-complete). Closed under union, intersection, complement.
• Example: $L = \{a^n b^n c^n \mid n \ge 1\}$
  • Grammar: $S \rightarrow aBC \mid aSBC$, $CB \rightarrow BC$, $aB \rightarrow ab$, $bB \rightarrow bb$, $bC \rightarrow bc$, $cC \rightarrow cc$
  • Generates $a^n b^n c^n$ by expanding and reordering

Type-0: Recursively Enumerable (RE)

• Grammar: No restrictions (unrestricted).
• Automaton: Turing Machine (TM).
• Properties: Not closed under complement. Halting problem undecidable. Semi-decidable.
• Example: $L = \{\langle M \rangle \mid M \text{ halts on empty input}\}$ (Halting problem)
• Note: All computable languages are RE; recursive (decidable) are subset where TM always halts.

---

Summary Table with Examples

Type	Language	Grammar Example	Automaton
3 (REG)	$(a+b)^*$	$S \rightarrow aS \mid bS \mid \epsilon$	DFA
3 (REG)	$\{w \mid \#_0(w) \text{ even}\}$	$S \rightarrow 0S \mid 1A$, $A \rightarrow 0A \mid 1S$	DFA (2 states)
2 (CFL)	$\{a^n b^n\}$	$S \rightarrow aSb \mid \epsilon$	PDA
2 (CFL)	$\{ww^R\}$	$S \rightarrow aSa \mid bSb \mid \epsilon$	NPDA
1 (CSL)	$\{a^n b^n c^n\}$	(as above)	LBA
0 (RE)	Halting Problem	Unrestricted	TM

---

Practical Implications

• Type-3: Lexical analysis, regex matching
• Type-2: Syntax analysis (parsers), programming language grammars
• Type-1: Rare in practice; natural language features
• Type-0: Theoretical limits, computability

---

Final Answer

Chomsky hierarchy organizes languages by grammar restrictiveness: Type-3 (Regular) ⊂ Type-2 (CFL) ⊂ Type-1 (CSL) ⊂ Type-0 (RE), each with corresponding automaton (FA, PDA, LBA, TM). Examples: REG → DFA, CFL → PDA, CSL → LBA, RE → TM.