Hierarquia de Chomsky

Em termos gerais, para n Î {0, 1, 2, 3} pode-se afirmar que uma gramática de qualquer tipo pode ser classificada também como sendo de tipo menor, se for o caso, de acordo com a Hierarquia de Chomsky. Analogamente, uma linguagem do tipo n é caracterizada pela existência de alguma gramática do tipo n que a descreva, podendo ser também classificada como sendo do tipo menor, se for o caso. GR = Gramáticas Regulares GLC = Gramáticas Livres de Contexto GSC = Gramáticas Sensíveis ao Contexto GEF = Gramáticas com Estrutura de Frase

1. Gramáticas com Estrutura de Frase ou Tipo 0 São aquelas às quais nenhuma limitação é imposta. Obviamente, todo o universo das linguagens que se pode definir através dos …exibir mais conteúdo…

Gramáticas Livres de Contexto ou Tipo 2 Conceituam-se gramáticas livres de contexto como sendo 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
A Þ a onde A Î Vn, a Î (Vn U Vt)* . Segundo a hierarquia de Chomsky, esta classe de gramáticas é classificada como Livre de Contexto ou do Tipo 2. Denominam-se linguagens do tipo 2 aquelas que podem ser definidas através de gramáticas do tipo 2. Notar novamente a relação de inclusão: toda gramática ou linguagem do tipo 2 também é do tipo 1, e portanto do tipo 0. Outra maneira de se representar as Gramáticas Livres de Contexto é através da Forma Normal de Backus. As Linguagem Livres de Contexto também podem ser reconhecidas pelos Autômatos à Pilha.

Exemplo 1: G = ({S}, {a, +, *, (, )}, P, S) P = S Þ S * S S Þ S + S S Þ (S) S Þ a L(G) = conjunto das expressões aritméticas envolvendo *, +, ( ) e a. Um exemplo de cadeia formada por esta gramática é a * (a + a). Exemplo 2: G = ({S, A, B}, {a, b}, P, S) P : S Þ aB | bA A Þ a | aS | bAA B Þ b | bS | aBB L(G) = { x Î Vt+ | x contém número de a's igual ao número de b's } Exemplo 3: Processo inverso: dada L(G), determinar G. L(G) = {0n12n0m