Chomsky Hierarchy

The Chomsky hierarchy is a classification of formal grammars, and the languages they generate, into four nested levels of increasing generative power: regular, context-free, context-sensitive and unrestricted (or recursively enumerable) grammars, each level defined by specific restrictions on how its production rules may rewrite symbols. Linguist Noam Chomsky introduced the hierarchy in a 1956 paper, developed as part of his broader work formalizing the mathematical structure of human language and grammar. Each level of the hierarchy corresponds to a specific class of abstract computing machine capable of recognizing exactly the languages that level can generate, ranging from the simplest finite automata for regular languages up through the full power of a Turing machine for unrestricted grammars, connecting the classification directly to the theory of computation. The Chomsky hierarchy became a foundational organizing framework in both theoretical linguistics and computer science, particularly in the design of programming language syntax and compiler parsing algorithms, which typically rely on context-free grammars occupying the hierarchy's second level.