The Chomsky hierarchy is a hierarchy of classes of formal language
s. Regular language
s are the smallest set; context-free language
s are a superset
of these; context-sensitive
are a superset of those; computable
languages are again a superset.
They can be characterised by different types of devices used to recognise these languages: finite state automata, pushdown automata, linear bounded automata, and Turing machines, respectively.
They can also be characterized by classes of grammars defined through simple restrictions on the forms of grammar rules:
- arbitrary grammars can describe any language;
- by requiring the left hand side of rules to contain at most one nonterminal, we get context-sensitive grammars;
- by requiring left hand sides to consist of a single nonterminal, we get context-free grammars;
- by requiring all right hand sides to consist of a terminal followed by a nonterminal, we get the (left) regular grammars;
these four categories of grammars describe the four categories of languages of the Chomsky hierarchy.