Hierarquia de Chomsky
Para cada um desses tipos podem ser definidos diferentes tipos de máquinas (algoritmos, autómatos) que as podem reconhecer.
Quanto mais simples for a gramática, mas simples e eficiente é a máquina que reconhece essas linguagens.
Cada classe de linguagens do tipo-i contém a classe de linguagens tipo-(i+1) (i = 0;1; 2)
Esta hierarquia não traduz apenas as características formais das linguagens, mas também expressam os requisitos de computação necessários:
As máquinas de Turing processam gramáticas sem restrições (tipo-0);
Os autómatos linearmente limitados processam gramáticas dependentes do contexto (tipo-1);
Os autómatos de pilha processam gramáticas independentes do contexto (tipo-2);
Os autómatos finitos processam gramáticas regulares (tipo-3).
Last updated