Tabulate the Chomsky hierarchy of grammars with an example for each.

Question

Accepted Answer

## Answer

### Chomsky Hierarchy of Grammars

| Type | Grammar Name | Production Form $\alpha ightarrow \beta$ | Language Class | Automaton |
|---|---|---|---|---|
| **Type-0** | Unrestricted | No restriction on $\alpha,\beta$ (except $\alpha 
eq \epsilon$) | Recursively Enumerable (RE) | Turing Machine |
| **Type-1** | Context-Sensitive | $|\alpha| \le |\beta|$, $\beta$ has $\alpha$ in context | Context-Sensitive (CSL) | Linear Bounded Automaton |
| **Type-2** | Context-Free | $A ightarrow \gamma$, $A \in V$, $\gamma \in (V \cup T)^*$ | Context-Free (CFL) | Pushdown Automaton (PDA) |
| **Type-3** | Regular / Right-Linear | $A ightarrow aB \mid a$ (or left-linear) | Regular (REG) | Finite Automaton (DFA/NFA) |

### Examples

| Type | Example Grammar | Language Generated |
|---|---|---|
| **Type-0** | $S ightarrow aSb \mid \epsilon$ with unrestricted rules e.g. $aB ightarrow Ba$ | $\{a^n b^n c^n \mid n\ge0\}$ or any computable language |
| **Type-1** | $S ightarrow aBC \mid aSBC$, $CB ightarrow BC$, $aB ightarrow ab$, $bB ightarrow bb$, $bC ightarrow bc$, $cC ightarrow cc$ | $\{a^n b^n c^n \mid n\ge1\}$ |
| **Type-2** | $S ightarrow aSb \mid SS \mid \epsilon$ | $\{w \mid \#_a(w) = \#_b(w)\}$ (balanced parentheses) |
| **Type-2** | $S ightarrow (S) \mid SS \mid \epsilon$ | Balanced parentheses language |
| **Type-3** | $S ightarrow 0S \mid 1S \mid \epsilon$ | $\{0,1\}^*$ (all binary strings) |
| **Type-3** | $S ightarrow aS \mid bA$, $A ightarrow bA \mid b$ | $\{a^m b^n \mid m,n\ge1\}$ (right-linear) |

### Containment Relations
$$
	ext{REG} \subset 	ext{DCFL} \subset 	ext{CFL} \subset 	ext{CSL} \subset 	ext{RE} \subset 	ext{ALL}
$$

Each level strictly contained in the next (proper subsets).

### Notes
- **Type-0** = RE = recognized by TM; not all decidable.
- **Type-1** = CSL = decided by LBA (PSPACE-complete membership).
- **Type-2** = CFL = parsed in $O(n^3)$ (CYK); inherently ambiguous CFLs exist.
- **Type-3** = REG = recognized by FA/DFA; all decidable properties.

### Final Answer
Table above summarizes all four Chomsky types with production forms, language classes, automata, and concrete grammar examples.

Type	Example Grammar	Language Generated
Type-0	$S \rightarrow aSb \mid \epsilon$ with unrestricted rules e.g. $aB \rightarrow Ba$	$\{a^n b^n c^n \mid n\ge0\}$ or any computable language
Type-1	$S \rightarrow aBC \mid aSBC$ , $CB \rightarrow BC$ , $aB \rightarrow ab$ , $bB \rightarrow bb$ , $bC \rightarrow bc$ , $cC \rightarrow cc$	$\{a^n b^n c^n \mid n\ge1\}$
Type-2	$S \rightarrow aSb \mid SS \mid \epsilon$	$\{w \mid \#_a(w) = \#_b(w)\}$ (balanced parentheses)
Type-2	$S \rightarrow (S) \mid SS \mid \epsilon$	Balanced parentheses language
Type-3	$S \rightarrow 0S \mid 1S \mid \epsilon$	$\{0,1\}^*$ (all binary strings)
Type-3	$S \rightarrow aS \mid bA$ , $A \rightarrow bA \mid b$	$\{a^m b^n \mid m,n\ge1\}$ (right-linear)

Answer

Chomsky Hierarchy of Grammars

Examples

Containment Relations

Notes

Final Answer

Similar questions

Pocketly on Android