Gramática com estrutura de frase
Origem: Wikipédia, a enciclopédia livre.
Em Teoria da computação a Gramática com estrutura de frase é também conhecida como Tipo 0 da Hierarquia de Chomsky, que são aquelas às quais nenhuma limitação é imposta. O universo das linguagens que se podem definir através dos mecanismos gerativos definidos pela gramática corresponde exatamente ao conjunto das linguagens que esta classe de gramática é capaz de gerar.
| 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 |
