Impl. de métodos comp.

Chomsky Hierarchy

American linguist Noam Chomsky defined in 1956 a classification of languages in terms of four levels of complexity. This four-level hierarchy, called the Chomsky hierarchy, corresponds to four classes of machines [1].

The following table summarizes each of Chomsky's four types of grammars, the class of language it generates, and the type of machine that recognizes it.

Grammar Language Machine
Type 0
Unrestricted
grammar
\(L_{\texttt{RE}}\)
Recursively enumerable language
Turing machine (TM)
Type 1
Context-sensitive
grammar
\(L_{\texttt{CS}}\)
Context-sensitive language
Linear-bounded automaton (LBA)
Type 2
Context-free
grammar
\(L_{\texttt{CF}}\)
Context-free language
Pushdown automaton (PDA)
Type 3
Regular
grammar
\(L_{\texttt{Reg}}\)
Regular language
Finite automaton (DFA/NFA)

Each language of type \(i\) is a proper subset of the family of type \(i − 1\). The following diagram exhibits the relationship clearly:

Reference