Hierarquia de Chomsky

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 mecanismos generativos definidos pelas gramáticas corresponde exatamente ao conjunto das linguagens que esta classe de gramáticas é capaz de gerar. A esta classe de gramáticas, a hierarquia de Chomsky classifica como sendo a dasGramáticas com Estrutura de Frase ou Tipo 0. Chamam-se linguagens do tipo 0 todas as linguagens que podem ser geradas por alguma gramática do tipo 0. Para gramáticas do tipo 0, as produções são todas da forma a Þ b, a Î (Vn U Vt)+, b Î (Vn U Vt)*.

Exemplo: G = ({A, B, C}, {a, b}, P, A) P: A Þ BC BC Þ CB B Þ b C Þ a L(G) = {ba, ab} 2. Gramáticas Sensíveis ao Contexto ou Tipo 1 Se às regras de substituição for imposta a restrição de que nenhuma substituição possa reduzir o comprimento da forma sentencial à qual a substituição é aplicada, cria-se uma classe de gramáticas ditas sensíveis ao contexto. As gramáticas que obedecem a estas restrições pertencem, na hierarquia de Chomsky, ao conjunto das Gramáticas Sensíveis ao Contextoou do Tipo 1. Chamam-se linguagens do tipo 1 todas aquelas que podem ser geradas por alguma gramática do tipo 1. Note-se que todas as linguagens do tipo 1 podem ser geradas através de gramáticas com estrutura de frase ou