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.


  1. N. Chomsky, Three models for the description of language, IRE Trans. Info. Theory 2 (3) (1956), 113-124.
  2. 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

September 10 1997