Formal Grammars and the Chomsky Hierarchy

The previous lesson argued that language needs a generative model: a finite set of rules producing an infinite set of sentences. A formal grammar is exactly that, made precise.

It has a set of symbols, split into terminals, the actual words or characters, and non-terminals, abstract categories like noun phrase. It has a start symbol and a set of production rules, each saying that one string of symbols may be rewritten as another. You generate a sentence by starting from the start symbol and applying rules until only terminals remain.

A rule like "Sentence goes to NounPhrase VerbPhrase" expands one category into two. The set of all terminal strings you can reach is the language the grammar defines. Noam Chomsky's 1956 paper "Three Models for the Description of Language" introduced this framing and, with it, the question of how much a grammar's rules may be constrained.

Chomsky's insight was that restricting the form of the rules yields a hierarchy of exactly four language classes, each strictly contained in the next.

Type 3, regular grammars, allow the most restricted rules and define the regular languages. Type 2, context-free grammars, let any single non-terminal be rewritten regardless of its neighbours. Type 1, context-sensitive grammars, let a rewrite depend on surrounding symbols. Type 0, unrestricted grammars, allow any rule at all and define the recursively enumerable languages, everything a Turing machine can recognize.

The containment is strict: every regular language is context-free, every context-free language is context-sensitive, and so on, but each larger class contains languages the smaller one provably cannot express. Moving up the hierarchy buys descriptive power and costs computational efficiency. The entire question of where human language sits is a question of which rung it needs.

Each rung pairs with a class of abstract machine that recognizes exactly its languages, which is the most useful way to grasp what each class can do.

Regular languages are recognized by finite automata, machines with a fixed, finite memory. Context-free languages need a pushdown automaton, a finite automaton plus a stack, and that stack is precisely what lets it match nested structure like balanced brackets. Context-sensitive languages need a linear-bounded automaton, a Turing machine whose tape is limited to the input length. Recursively enumerable languages need a full Turing machine with unbounded tape.

The theme is memory. A finite automaton remembers only which of finitely many states it is in. Adding a stack gives bounded-depth recall of the past. A tape gives unbounded, rewritable memory. How much structure a language can have is exactly how much memory its recognizer needs.

Start at the bottom and climb. Could a regular grammar, a finite automaton, capture English syntax? No, and the reason is center embedding.

English permits nested dependencies: in "the cat that the dog chased ran", the verb "ran" must agree with "cat", across the embedded clause "that the dog chased". Nest another clause and the matching spans further. This is the pattern of a language like a-to-the-n followed by b-to-the-n, where you must count how many openings you saw to match the same number of closings.

A finite automaton has only finitely many states, so it cannot count to an unbounded depth; past some nesting level it loses track. This is a classic consequence of the pumping lemma for regular languages. Human syntax has unbounded nested dependencies in principle, so it is provably beyond the regular class. The first rung is too low.

The natural home for syntax is the next rung, the context-free grammar, and for decades it was taken as the model of sentence structure.

A context-free rule rewrites a single non-terminal no matter what surrounds it, which is enough to express nesting: a rule like "NounPhrase goes to NounPhrase RelativeClause" is recursive, generating arbitrarily deep embedding, and the recognizer's stack handles the matching a finite automaton could not. Context-free grammars capture the constituency of English, the way words group into phrases that group into larger phrases, and they parse efficiently, in cubic time, with algorithms like CKY.

The same formalism is what compilers use for programming-language syntax, the subject of the comp-parsing-and-asts lesson. Programming languages were deliberately designed to be context-free so they could be parsed reliably. The interesting discovery is that human language, which nobody designed, is not quite so obliging.

Whether natural language is context-free was debated for years, because most constructions are, and finding a genuine counterexample is subtle. The decisive one came from Stuart Shieber in 1985.

His paper "Evidence against the context-freeness of natural language", in Linguistics and Philosophy, used Swiss German. That dialect allows cross-serial dependencies: a series of noun phrases followed by a series of verbs, where the first noun matches the first verb, the second the second, and so on, with the case each verb assigns tracked across the whole span. This is the crossing pattern, unlike the nesting a context-free grammar handles, and Shieber showed via a formal argument that no context-free grammar can generate it.

Around the same time Christopher Culy made a parallel argument from word formation in Bambara. Together they settled it: at least some human languages are strictly beyond context-free.

So natural language is above context-free. Is it all the way up at context-sensitive, the next named rung? That would be bad news, because context-sensitive recognition is far more expensive, and human sentences do not seem to need that much power.

Aravind Joshi proposed the resolution: natural language occupies a class just barely above context-free, which he called mildly context-sensitive. It adds exactly enough power to handle limited crossing dependencies like Swiss German, while keeping efficient, polynomial-time parsing and other well-behaved properties.

Several independently designed formalisms turned out to define this same class, which is strong evidence it is the right one: Joshi's own Tree-Adjoining Grammar, and Combinatory Categorial Grammar among them. The lesson is that human language sits in a narrow, specific band of the hierarchy, more than context-free but far short of the full power a Turing machine allows.

Assembling the ladder with its machines, its costs, and its linguistic role:

The useful reading is that each level of language finds its natural home, and no more. Sound and word structure sit at the bottom, plain syntax at context-free, and full human syntax just above it. Nothing in language appears to require the top two rungs, whose cost is prohibitive anyway. This map is the reference the last lesson holds neural networks against: to understand a language model, you ask which rung its architecture can reach.

You now have the central tool of formal computational linguistics: a ladder of grammar classes, each tied to a machine and a memory model, with human language pinned to a specific narrow band, mildly context-sensitive, above context-free and far below the top.

Two threads run into the rest of the path. Downward, the regular languages at the bottom are exactly where morphology lives, and the next lesson shows finite-state machines handling word structure with real elegance. Upward and forward, the same hierarchy becomes a measuring stick for neural networks: a recurrent network or a transformer recognizes some class of the languages on this ladder, and knowing which one predicts what it can learn.

The abstract question of how much memory a pattern requires, which felt purely theoretical here, turns out to have sharp, testable consequences for the language models in use today.