Chomsky hierarchy

Summary

The Chomsky hierarchy sorts formal grammars into four types by the shape of their rules, and the languages they generate into four nested classes. From the largest class to the smallest, these are the recursively enumerable languages (type 0) and the context-sensitive languages (type 1). They are followed by the context-free languages (type 2) and the regular languages (type 3). Each class matches a kind of machine: Turing machines, linear bounded automata, pushdown automata and finite automata. All the inclusions between consecutive classes are strict.