Chomsky Hierarchy

Not all grammars are equally powerful. The Chomsky hierarchy (Noam Chomsky,
1965; Definition 7.3.1, notes p. 140) classifies grammars by the shape of their
production rules. Each level is more restrictive — and easier to parse.

The four levels, from least to most restrictive:

- Type 0 — Unrestricted (phrase-structure grammars). Heads contain at
least one nonterminal; bodies are arbitrary strings. Maximum power.

- Type 1 — Context-sensitive. Bodies have no fewer symbols than heads:
$|b| \ge |h|$. (Exception: $S \to \epsilon$ is allowed.) The rewrite depends on
the surrounding context.

- Type 2 — Context-free (CFG). Heads are a single nonterminal:
$A \to b$ for $A \in N$. The rewrite does not depend on context. CFGs cover
most programming language syntax.

- Type 3 — Regular (REG). Heads are a single nonterminal; bodies are
empty or a single terminal, optionally followed by a single nonterminal.
Equivalent to finite-state machines. Minimum power; easiest to parse.

The hierarchy is strict: every regular language is context-free, every
context-free language is context-sensitive, every context-sensitive language is
unrestricted. Each containment is strict (there are languages at level $i$ that
are NOT at level $i+1$).

Classic examples:
- $\{a^n b^n c^n \mid n \ge 0\}$ — context-sensitive (Type 1). Cannot be CFG.
- $\{a^n b^n \mid n \ge 0\}$ — context-free (Type 2). Cannot be regular.
- $\{a^n \mid n \ge 0\}$ — regular (Type 3).

For SMAI and most AI applications, context-free grammars are the sweet spot:
expressive enough for most languages, parsing algorithms run in $O(n^3)$ (Theorem
7.3.14, notes p. 173).

The language $L = \{a^n b^n c^n \mid n \geq 1\}$ is context-sensitive (Type 1) — it cannot be generated by a context-free grammar.

A context-sensitive grammar for $L$:

The rule cB → Bc swaps c to the right of B — needed to gather all the cs at the end. This is the kind of cross-serial dependency that distinguishes context-sensitive from context-free.

Observation. Natural languages (English, German, ...) are believed to be context-sensitive in general. Crucially, humans parse them in real time — despite the theoretical worst-case complexity. This is the 'real-time parsing puzzle' and motivates incremental / psycholinguistic models of parsing.

The language $L = \{a^n \mid n \geq 0\}$ is regular. A Type-3 grammar:

The recursive rule S → aS produces any number of as; the base case S → ε (empty string) terminates. This is the simplest possible non-trivial regular language.