nLab Chomsky hierarchy

Formal grammars come in a hierarchy of expressive power, first introduced by Noam Chomsky.

• Type-0 grammars, also known as unrestricted grammars, generate the recursively enumerable languages, and correspond to Turing machines.
• Type-1 grammars are also called context sensitive grammars, and correspond to linear-bounded nondeterministic Turing machines.
• Type-2 grammars are also called context free grammars, and correspond to nondeterministic pushdown automata.
• Type-3 grammars generate regular languages, and are equivalent to regular languages and finite-state automata.