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
|