Chomsky Hierarchy Definition/Meaning:
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. The 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 definable by
primitive recursive functions. Types 2
and 3 are significant in providing abstractions of the computational
ideas of iteration and recursion respectively.
|
