In his seminal 1956 paper, Noam Chomsky established mathematical linguistics by organizing all generative grammars into a strict nested hierarchy based on the syntactic constraints placed upon their rewriting rules. This four-tier taxonomy establishes an exact correspondence between abstract mathematical languages and the theoretical automata required to parse them.
1. Formal Definition of Generative Grammars
A formal grammar (G) is defined mathematically as a 4-tuple:
[
G = langle V_N, V_T, P, S
angle
]
where:
- (V_N) is a finite set of non-terminal alphabet symbols (syntactic variables such as (S, NP, VP)).
- (V_T) is a finite set of terminal alphabet symbols (lexical words or characters), disjoint from (V_N) ((V_N cap V_T = mptyset)).
- (P) is a finite set of production (rewriting) rules of the general form (alpha o beta), where (alpha in (V_N cup V_T)^+ V_N (V_N cup V_T)^*) and (beta in (V_N cup V_T)^*).
- (S in V_N) is the designated start symbol.
The language generated by the grammar (L(G)) is the set of all terminal strings derived from (S) via finite applications of production rules: (L(G) = { w in V_T^* mid S Rightarrow^* w }).
2. The Four Levels of the Chomsky Hierarchy
By progressively restricting the structural form of the production rules (alpha o beta), Chomsky delineated four foundational classes of formal languages:
Type 3: Regular Grammars (Finite Automata)
Every production rule is restricted to right-linear ((A o w B) or (A o w)) or left-linear form, where (A, B in V_N) and (w in V_T^*). Regular grammars generate languages recognized equivalently by Deterministic and Non-Deterministic Finite State Automata (DFA/NFA). They cannot maintain unbounded memory or count arbitrary nested structures; the classic language (L = { a^n b^n mid n ge 1 }) is provably non-regular via the Pumping Lemma.
Type 2: Context-Free Grammars (Pushdown Automata)
Production rules are restricted to the form (A o gamma), where the left-hand side is strictly a single non-terminal (A in V_N), and (gamma in (V_N cup V_T)^*). The replacement of (A) is completely context-free, independent of neighboring symbols. Context-Free Grammars (CFGs) are recognized by Non-Deterministic Pushdown Automata (NPDA) equipped with a single Last-In-First-Out (LIFO) stack. CFGs successfully parse balanced parentheses, arithmetic expressions, and the canonical nested structures of programming languages and natural language phrase hierarchies.
Type 1: Context-Sensitive Grammars (Linear-Bounded Automata)
Production rules take the form (alpha A beta o alpha gamma beta), where the non-terminal (A) can be rewritten as (gamma) only in the specific context bounded by (alpha) and (beta). A non-contracting constraint is enforced: (|gamma| ge 1) (i.e., (|beta| ge |alpha|)). Context-Sensitive Languages are parsed by Linear-Bounded Automata (LBA)—Turing machines whose tape length is strictly bounded by a linear function of the input length (k cdot |w|). The language (L = { a^n b^n c^n mid n ge 1 }), capturing cross-serial dependencies in languages like Swiss-German, is context-sensitive.
Type 0: Unrestricted Grammars (Turing Machines)
Production rules (alpha o beta) have no structural restrictions other than (alpha
eq psilon). Type 0 grammars generate the entire class of Recursively Enumerable Languages, recognized by universal Turing Machines. Membership in Type 0 languages is undecidable in general, falling subject to Turing’s Halting Problem.
3. Where Does Human Natural Language Reside?
A central question of 20th-century computational linguistics was determining natural language’s exact position on the Chomsky hierarchy. Chomsky proved in 1957 that natural languages are strictly non-regular due to unbounded nested center-embedding:
[
ext{“The rat [that the cat [that the dog chased] killed] ate the malt.”}
]
In 1985, Stuart Shieber definitively proved that natural language is also not strictly context-free. Analyzing cross-serial case-marking dependencies in Swiss-German subordinate clauses:
[
dots ext{mer em Hans es huus hälfed aastriiche} quad ( ext{dative } NP_1 ext{ acc } NP_2 dots V_1 V_2)
]
Shieber proved that natural language possesses overlapping, non-nested cross-serial dependencies isomorphic to ({ a^n b^m c^n d^m }). Consequently, human natural language is classified mathematically as mildly context-sensitive, occupying the computational space parsed efficiently by Tree-Adjoining Grammars (TAG) and Combinatory Categorial Grammars (CCG) in polynomial time (mathcal{O}(n^6)).
