| Teoria de autômatos: linguagem formal e gramática formal
|
Hierarquia
Chomsky
|
Gramática
|
Linguagem
|
Reconhecedor
|
| Tipo-0
|
Irrestrita
|
Recursivamente enumerável
|
Máquina de Turing
|
| --
|
--
|
Recursiva
|
Máquina de Turing que sempre para
|
| Tipo-1
|
Sensível ao contexto
|
Sensível ao contexto
|
Autômato linearmente limitado
|
| Tipo-2
|
Livre de contexto
|
Livre de contexto
|
Autômato com pilha
|
| Tipo-3
|
Regular
|
Regular
|
Autômato finito
|