Reconhecedores

Keywords: Reconhecedores, Autômatos, Hierarquia de Chomsky, Máquina de Turing

Como alternativa para a definição de uma linguagem, utilizam-se Reconhecedores de uma linguagem. Através dos reconhecedores é possível submeter uma cadeia de símbolos a um teste de aceitação capaz de determinar se tal cadeia pertence ou não à linguagem em questão.

Tabela de Correspondência
Gramáticas	Reconhecedores
Com estrutura de Frase ou Tipo 0	Máquina de Turing
Sensíveis ao Contexto ou Tipo 1	Máquina de Turing com memória limitada
Livres de Contexto ou Tipo 2	Autômatos a Pilha
Regulares ou Tipo 3	Autômatos Finitos

Keywords: Reconhecedores, Autômatos, Hierarquia de Chomsky, Máquina de Turing