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:

1. As máquinas de Turing processam gramáticas sem restrições (tipo-0);

2. Os autómatos linearmente limitados processam gramáticas dependentes do contexto (tipo-1);

3. Os autómatos de pilha processam gramáticas independentes do contexto (tipo-2);

4. Os autómatos finitos processam gramáticas regulares (tipo-3).