Hierarquia de Chomsky
Origem: Wikipédia, a enciclopédia livre.
Hierarquia de Chomsky é a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis, sendo que os dois últimos níveis são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores.
A classificação das gramáticas começam pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é conseqüentemente uma gramática de tipo n - 1.
Índice |
[editar] Gramática com estrutura de frase
Também conhecida como Tipo 0, 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.
[editar] Gramáticas sensíveis ao contexto
Também conhecida como Tipo 1. Se as regras de substituição forem sujeitas à restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe chamada sensíveis ao contexto ou tipo 1.
[editar] Gramáticas livres de contexto
Também conhecida como de Tipo 2, são aquelas em que é levantado o condicionamento das substituições impostas pelas regras definidas pelas produções. Este condicionamento é eliminado impondo às produções uma restrição adicional, que restringe as produções à forma geral
onde 
e 
[editar] Forma Normal de Backus
Forma Normal de Backus ou somente FNB, é uma outra forma de representar as produções de Gramáticas livres de contexto.
Onde, 
é substituído por ::= e os não terminais por <"nome" >.
Ela é usada para definir gramáticas com o lado esquerdo de cada regra composto por um único símbolo não terminal.
Exemplo:
<Y> ::= y1
<Y> ::= y2
:
<Y> ::= yn
escreve-se: <Y> ::= y1| y2| ...| yn
[editar] Gramáticas regulares
Também conhecida como de Tipo 3, é uma restrição sobre a forma das produções, pode-se criar uma nova classe de gramáticas de grande importância no estudo dos compiladores por possuírem propriedades adequadas para a obtenção de reconhecedores simples. Que também podem ser denominada de Expressão regular.
| 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 |
