Why a linguist built a cornerstone of CS (history)

Parent: chomsky-hierarchy

It is genuinely surprising that the automata hierarchy came from Noam Chomsky, a linguist (1956, Three Models for the Description of Language; Syntactic Structures, 1957). The bridge was a specific argument turned into mathematics.

The target: language is not finite-state

1950s linguistics ran on behaviorism (Skinner) and structuralism, and Shannon's information theory had made finite-state / Markov models of language fashionable — a sentence as a stochastic chain of words. Chomsky's decisive move was a mathematical refutation:

Natural language has unbounded nested (center-embedding) dependencies — "the rat the cat the dog chased killed ate the malt" — where an opening piece must match a closing piece arbitrarily far away. A finite automaton has no memory to count the nesting, so no finite-state (Markov) model can generate exactly the grammatical sentences.

This is precisely the [[regular-languages|aⁿbⁿ argument]]: language needs at least a stack (context-free). A claim about the human mind became a theorem about automata.

Generative grammar → the hierarchy

Chomsky reframed a grammar as a formal generative system — rewriting rules that produce all and only the grammatical strings (drawing on Emil Post's production/rewriting systems and Thue). The hierarchy (Types 0–3) is the answer to a purely mathematical question that linguistics forced: "how much generative power does each restriction on the rewrite rules buy?" — and it lined up exactly with classes of automata (memory).

Why it mattered to computer science

The formalization boomeranged into CS:

• Context-free grammars became programming-language syntax — Backus–Naur Form (ALGOL 60) is essentially a CFG; the whole theory of parsing and compilers is built on Types 2–3.
• Chomsky–Schützenberger (with a mathematician) gave CFLs an algebraic theory.

So a cognitive-science question ("what is human syntax?") seeded compiler theory — the non-trivial part is exactly that a humanities-side question produced a foundational computational framework, via the move of formalizing grammar as a rewriting system and asking about its power.

The lasting empirical claim

The hierarchy isn't just taxonomy: placing human language at mildly context-sensitive (above CF, below full CS) is a substantive, mathematically precise claim about the mind — the kind of bridge between empirical science and formal computation that rarely happens.