The Chomsky hierarchy and normative grammar (1956)

The Chomsky hierarchy is a classification of formal grammars — and of the languages they generate — into four nested levels, from Type 0 (unrestricted) to Type 3 (regular), ordered by their generative power. It was introduced by Noam Chomsky in his 1956 paper “Three models for the description of language” and given its precise mathematical form in 1959 in “On Certain Formal Properties of Grammars”. Each level of the hierarchy corresponds to a class of abstract machines (automata) that recognize exactly the languages of that level, which made the hierarchy a cornerstone of both theoretical linguistics and computer science.

In this framework, a language is understood as a set (finite or infinite) of sentences, each finite in length and constructed out of a finite set of elements. A grammar is a finite set of rewriting rules that generates exactly the sentences of that language — no more and no fewer. The four types differ only in how much freedom those rules are allowed.

The four types of grammars

The hierarchy is strictly nested: every regular language is context-free, every context-free language is context-sensitive, and every context-sensitive language is recursively enumerable — but none of these inclusions works the other way around.

Type 0 — unrestricted grammars: no constraints on the production rules. They generate the recursively enumerable languages — everything that a Turing machine can recognize. This is the outermost and most powerful class; in general there is no procedure that decides whether an arbitrary string belongs to a Type 0 language.
Type 1 — context-sensitive grammars: a rule may rewrite a symbol only in a specified context, and the right-hand side of a rule may never be shorter than the left-hand side. They generate the context-sensitive languages, recognized by linear-bounded automata — Turing machines whose working tape is limited to the length of the input. A textbook example is aⁿbⁿcⁿ: equal numbers of a’s, b’s and c’s, in that order.
Type 2 — context-free grammars: every rule rewrites a single symbol, regardless of what surrounds it. They generate the context-free languages, recognized by pushdown automata — finite machines equipped with a stack. A textbook example is aⁿbⁿ, or the language of correctly balanced brackets. The syntax of most programming languages is defined by context-free grammars.
Type 3 — regular grammars: the most restricted class, in which each rule may produce at most one terminal symbol followed by at most one non-terminal. They generate the regular languages, recognized by finite automata and described by regular expressions — for example, “all strings of a’s and b’s that end in b”.

1956: why the hierarchy was created

In the early 1950s, the dominant mathematical model of language came from information theory: a sentence was viewed as the output of a Markov process that picks each word based on the words immediately before it — a finite-state, probabilistic view aligned with behaviorist psychology. Chomsky’s 1956 paper “Three models for the description of language” (IRE Transactions on Information Theory) compared three candidate models: the finite-state model, phrase-structure grammars, and transformational grammar.

His key negative result was that English cannot be adequately described by a finite-state model, because English allows unbounded nested dependencies: constructions like “if … then” and “either … or” can be embedded inside one another indefinitely, and a finite-state device has no memory to keep track of the nesting. A year later, Syntactic Structures (1957) popularized the argument, and the 1959 paper defined the full four-level hierarchy with mathematical rigor. The hierarchy quickly became fundamental to compiler design and the theory of computation — arguably its most lasting practical legacy.

Where do human languages fit?

Contrary to a popular simplification, Chomsky did not claim to prove that human languages occupy any particular level. His 1956 result was negative: natural languages are not regular (not Type 3). Whether they are context-free (Type 2) remained an open question for three decades, until Stuart Shieber showed in 1985, using cross-serial verb dependencies in Swiss German, that at least one natural language is provably not context-free.

The consensus position today, going back to Aravind Joshi, is that natural languages are mildly context-sensitive: slightly beyond Type 2, but far below the full power of Type 1, let alone Type 0. For Chomsky, the formal apparatus served a larger point: since every child converges on such a system without explicit instruction, the capacity for grammar must be part of our biological endowment — the thesis of universal grammar and the language acquisition device, developed in his nativist theory of language.

Generative grammar vs normative grammar

“Grammar” is one of the most overloaded terms in language learning, and the hierarchy helps untangle it. In Chomsky’s sense, a grammar is a formal device that generates a language — think of an assembly line that produces strings of symbols. It describes which sentences are possible, and says nothing about which are “proper”.

Normative (prescriptive) grammar is something else entirely: a set of social conventions that dictate how a language should be used, especially in formal writing — standards of correctness for vocabulary, syntax, spelling and punctuation. It is codified by institutions, style guides and school curricula, and it changes with fashion and authority, not with mathematical proof.

Between the two sits the grammar that native speakers actually carry in their heads: an implicit, internalized system — what Chomsky calls competence — that lets a speaker judge instantly that a sentence sounds right or wrong, even if they cannot state a single rule. A generative grammar is a scientist’s explicit model of that unconscious knowledge.

What this means for language learning

The grammar a learner ultimately wants is not the normative rulebook but the native speaker’s intuition: the internalized system that produces and evaluates sentences automatically. That system is acquired implicitly, by processing large numbers of meaningful sentences, not by memorizing prescriptive rules — which is why Chomsky’s work reshaped language teaching, shifting its goal from rule-drilling toward building competence. Learning methods built on whole sentences and systematic repetition, such as the Taalhammer method, follow directly from this insight: you feed the internal grammar examples until it starts generating on its own.

Frequently asked questions

What is the Chomsky hierarchy in simple terms?

It is a ranking of grammars by power. Type 3 (regular) grammars can only handle simple patterns; Type 2 (context-free) can handle nesting, like brackets within brackets; Type 1 (context-sensitive) can match several counts at once; Type 0 can describe anything a computer can compute. Each level contains all the levels below it.

Why is the Chomsky hierarchy important in computer science?

Because each level maps to a machine model: regular expressions and lexical analyzers live at Type 3, programming-language parsers at Type 2, and the theory of computability at Type 0. The hierarchy tells engineers which tool is sufficient for which task — and it is still used today, for example to probe what neural language models can and cannot compute.

Did the hierarchy prove that language is innate?

No. The hierarchy is a neutral mathematical tool. Chomsky’s innateness argument rests on the poverty of the stimulus — children acquire a rich grammar from limited evidence — for which the hierarchy provided a formal backdrop, by showing how much structure any adequate grammar of a human language must contain.

Sources

Noam Chomsky, “Three models for the description of language”, IRE Transactions on Information Theory 2(3), 1956.
Noam Chomsky, “On Certain Formal Properties of Grammars”, Information and Control 2(2), 1959.
Noam Chomsky, Syntactic Structures, Mouton, 1957.
Stuart M. Shieber, “Evidence Against the Context-Freeness of Natural Language”, Linguistics and Philosophy 8, 1985.
Aravind K. Joshi, “Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions?”, in Natural Language Parsing, Cambridge University Press, 1985.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2006.