Other meanings of Chomsky hierarchy
Formal language theory
The Chomsky hierarchy is a classification of formal grammars and the languages they generate, introduced by linguist Noam Chomsky in the 1950s. It consists of four types—Type 0 (unrestricted), Type 1 (context-sensitive), Type 2 (context-free), and Type 3 (regular)—each defining a progressively restricted class of generative rules. The hierarchy is fundamental to theoretical computer science, linguistics, and automata theory, linking grammar types to computational models such as Turing machines, linear-bounded automata, pushdown automata, and finite automata.12
The hierarchy is defined by increasing restrictions on the form of production rules in a formal grammar. Type 0 grammars have no restrictions on production rules; they generate the class of recursively enumerable languages and correspond to Turing machines. Type 1 grammars, or context-sensitive grammars, allow productions of the form αAβ → αγβ where γ is non-empty, generating context-sensitive languages recognized by linear-bounded automata. Type 2 grammars, context-free grammars, have productions A → γ, where A is a single nonterminal, generating context-free languages that are recognized by pushdown automata. Type 3 grammars, regular grammars, restrict productions to right-linear or left-linear forms, generating regular languages recognized by finite automata.13 Each type strictly contains the next: Regular ⊂ Context-free ⊂ Context-sensitive ⊂ Recursively enumerable.
In computer science, the Chomsky hierarchy is essential for compiler design, programming language specification, and formal verification. Context-free grammars (Type 2) are widely used to define the syntax of programming languages, while regular expressions (Type 3) are used for lexical analysis. In linguistics, the hierarchy provides a framework for modeling natural language syntax; Chomsky argued that natural languages are not regular (Type 3) and require at least context-free power, but many phenomena suggest they are mildly context-sensitive, beyond strict Type 2.24 The hierarchy also underpins automata theory, linking each grammar type to a mathematical model of computation, and informs the study of computational complexity by classifying problems by the formal language they represent.
Several extensions to the Chomsky hierarchy have been proposed. The Chomsky–Schützenberger hierarchy, developed by Chomsky and Marcel Schützenberger, characterizes context-free languages in terms of a theorem relating them to regular languages and Dyck languages. Indexed grammars, introduced by Alfred Aho, extend context-free grammars with stack-like structures, generating languages between context-free and context-sensitive. Mildly context-sensitive grammars, such as tree-adjoining grammars, are designed to handle natural language constructions while remaining polynomially parsable. Other hierarchies, like the Grzegorczyk hierarchy or the Arden hierarchy, classify languages by computational complexity rather than grammar form, but the Chomsky hierarchy remains the most influential classification in formal language theory.56
Chomsky’s original 1956 paper presented only three types (without Type 0); the fourth type was added in his 1959 work. The hierarchy is often depicted as a containment diagram, but it does not cover all possible formal languages — for instance, the class of recursive languages lies between Type 0 and Type 1 but is not a distinct level in the original hierarchy. The term “Type 4” is sometimes used for regular languages, but this is non-standard. In computational biology, the hierarchy has been applied to model RNA secondary structure. The hierarchy also has a surprising connection to the field of L-systems, which are similar to grammars but used to model plant growth. The hierarchy is independent of the choice of grammar formalism: equivalent grammars produce the same language classes.17
The Chomsky hierarchy remains a foundational concept in both theoretical computer science and linguistics, with ongoing relevance in fields such as computational biology and natural language processing.
Help improve the encyclopedia. Reports go straight to the site manager.