A tutorial on finite automata
On Language Classification
Starting from the definition of grammars, Chomsky introduced a classification into four classes:
-
type-0 languages, also called recursive enumerable
-
type-1 languages, also called context sensitive
-
type-2 languages, also called context free
-
type-3 languages, also called regular
The type-0 class is the most general one. The other classes are obtained imposing restrictions on the productions or rules that are to be considered. The type-0 class includes the type-1 class, which includes the type-2 class, which in turn includes the type-3 class of languages.
Back to index