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, they correspond to Turing machines.
• Type-1 grammars are also called context sensitive grammars, they correspond to linear-bounded nondeterministic Turing machines.
• Type-2 grammars are also called context free grammars, they correspond to nondeterministic pushdown automata.
• Type-3 grammars generate regular languages, they are equivalent to regular languages and finite-state automata.