Chomsky hierarchy

A classification of formal grammars and languages into four classes, from unrestricted grammars to regular grammars, ordered by expressive power.

Formal grammar: A set of rules that generates strings in a formal language. Each class in the hierarchy is defined by restrictions on grammar rules.
Unrestricted grammar: A grammar whose productions have no general form restriction beyond requiring a nonterminal on the left. It occupies the hierarchy’s most expressive class, generating recursively enumerable languages.
Pumping lemma for regular languages: A necessary property of every regular language, used to prove that particular languages are not regular. It exposes the expressive limits of the hierarchy’s bottom class.
Noam Chomsky: An American linguist whose work shaped generative grammar and modern theoretical linguistics. His 1956 classification gave the hierarchy its name and its original grammatical framing.
Compiler: A program that translates source code into another representation, often machine code. Compiler syntax is commonly specified with context-free grammars and parsed with related methods.
Formal language: A set of finite strings over a specified alphabet. The hierarchy classifies languages according to the grammars that generate them.
Context-sensitive grammar: A grammar whose productions do not shorten strings, apart from an optional empty-string rule. Its length-preserving constraint places it below unrestricted grammars and above context-free grammars.
Pumping lemma for context-free languages: A necessary property of context-free languages used to show that some languages are not context-free. It distinguishes context-free power from languages requiring higher levels.
Formal language theory: The mathematical study of languages defined by rules, machines, and algebraic properties. The hierarchy became a foundational classification within this broader theory.
Parsing: The process of analyzing a string according to a grammar’s structural rules. Grammar classes constrain which parsing algorithms and computational resources are available.

Linked from 7 pages

Context-free languageNarrower topic: It places context-free languages between regular and context-sensitive languages.