Chomsky hierarchy
Published:
The Chomsky hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956. It is also named after Marcel-Paul Schützenberger, who played a crucial role in the development of the theory of formal languages.
It is used also to measure the power of a computational model by studying the class of formal languages that the model can generate.
See also
Artificial Intelligence, Computer Complexity, Turing Machines, Automata theory, Theory of computation