Reconhecedores
Origem: Wikipédia, a enciclopédia livre.
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 |
| Teoria de Autômatos: Linguagem formal e gramática formal | |||
|---|---|---|---|
| Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
| Tipo-0 | Estrutura de frase | Recursivamente enumerável | Máquina de Turing |
| -- | Estrutura de frase | Recursiva | Máquina de Turing |
| Tipo-1 | Sensíveis ao contexto | Sensíveis ao contexto | Máquina de Turing com memória limitada |
| Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
| Tipo-3 | Regular | Regular | Autômato finito |
