Chomsky hierarchy
Chomsky hierarchy A series of four classes of formal languages whose definition in 1959 by Noam Chomsky marked the beginning of formal language theory, and that have ever since remained central to the subject. In increasing complexity they are called type 3, type 2, type 1, and type 0, each one a subclass of the next. Each type can be defined either by a class of grammars or by a class of automata, as indicated in the table. Type 0 consists of all recursively enumerable languages. Type 1 is a subclass of the languages recognizable by primitive recursive functions. Languages in types 2 and 3 can be recognized by a Turing machine in cubic and linear time, respectively.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
Chomsky hierarchy