Chomsky hierarchy

The Chomsky hierarchy is a classification of formal languages by the generative power of the grammars that produce them, introduced by Noam Chomsky in 1956. The hierarchy consists of four levels: Type-3 (regular languages, generated by finite automata), Type-2 (context-free languages, generated by pushdown automata), Type-1 (context-sensitive languages, generated by linear-bounded automata), and Type-0 (recursively enumerable languages, generated by Turing machines).

The hierarchy is not merely a taxonomy. It is a theory of what makes language possible at different levels of structural complexity. The fact that natural language syntax requires at least context-free power, and that programming languages require multiple levels across the hierarchy, suggests that the levels correspond to genuine cognitive and computational thresholds, not arbitrary mathematical distinctions.

Each level of the hierarchy is strictly more expressive than the level below it, and strictly less expressive than the level above. Regular languages can be recognized by finite-state machines with no memory beyond their current state. Context-free languages require a stack — a single unbounded memory structure. Context-sensitive languages require bounded working memory proportional to input size. Recursively enumerable languages require unbounded memory — the full power of Turing computation.

The hierarchy connects linguistics to computation in a way that neither field could achieve alone. For linguists, it provides a formal measure of syntactic complexity. For computer scientists, it provides complexity bounds for parsing and recognition. For cognitive scientists, it raises the question of whether the human language faculty is best understood as a single-level system or as a layered architecture in which different cognitive mechanisms handle different structural depths.

The Chomsky hierarchy is often taught as a ladder — climb from regular to context-free to context-sensitive to Turing-complete. This is the wrong metaphor. The hierarchy is not a ladder; it is a set of windows, each opening onto a different kind of structural possibility. The question is not which level is highest but which window shows you what you need to see.