Computability and Complexity/Formal Languages/Chomsky Hierarchy
Chomsky Hierarchy[edit | edit source]
The Chomsky hierarchy is a collection of four classes of formal languages, each of which is a proper subset of the classes above it, and each of which corresponds to both a generating grammar and to a recognizing machine. This hierarchy developed primarily from the works of Noam Chomsky and Marcel-Paul Schutzenberger in the late 1950s on mechanistic linguistics and formal languages. The various levels of the hierarchy have proven useful in both theoretical and applied computer science, as they connect to Alan Turing's work on algorithms and computability, and in compiler design.
Each level of this hierarchy consists of a class of formal languages, a class of generative grammars, each of which produces a language in the associated class, and a class of machines, each of which recognizes a language in the associated class. At each level of the hierarchy, the rules for the generative grammar become more restrictive, making each class of languages a subset of the classes above it. Those four classes, from most restrictive to least restrictive, are: