The Chomsky Hierarchy
The Chomsky Hierarchy is a classifcation of languages classes invented
by Noam Chomsky, the American linguist and
philosopher. Chomsky defined four different classes of grammers,
which he called Type 0, Type 1, Type 2, and Type 3.
Type 0 grammars are today often called unrestricted grammars.
They generate the recursively enumerable languages.
Type 1 grammars are now usually called context-sensitive grammars.
They generate the context-sensitive languages, or CSL's.
Type 2 grammars are now referred to as context-free grammars.
They generate the context-free languages.
Type 3 grammars are now called linear grammars, and they generate
the regular languages
Each of these classes is strictly contained in the larger class above
it.
Sources
- N. Chomsky, Three models for the description of language,
IRE Trans. Info. Theory 2 (3) (1956), 113-124.
- N. Chomsky, On certain formal properties of grammars,
Information and Control 2 (3) (1959), 137-167.
Back to Theory of Computing Hall of Fame Main Page
Back to CS 462 home page