Baixe o app para aproveitar ainda mais
Prévia do material em texto
PROPRIEDADES DAS LINGUAGENS LIVRES DE CONTEXTO Marcelo Guerra INTRODUÇÃO Simplificação de GLC’s Facilitar a prova de propriedades das LLC’s. Se uma linguagem é LLC, ela tem uma gramática em alguma forma especial. Lema do bombeamento para LLC’s. Serve para mostrar que uma linguagem não é livre de contexto. A mesma idéia do Teorema 4.1 para linguagens regulares é utilizada. Propriedades de fechamento e de decisão. Algumas propriedades de fechamento das linguagens regulares não são verdadeiras para as LLC’s. FORMAS NORMAIS PARA GLC’S Vamos mostrar que toda LLC (sem ) é gerada por uma GLC na qual todas as produções são da forma: A BC ou A a A, B, e C são variáveis e a é um terminal Esta é a chamada Forma Normal de Chomsky Para chegar a ela, é necessário realizar uma série de simplificações preliminares. SIMPLIFICAÇÕES 1. Eliminar as ε-produções Da forma A ε para alguma variável A 2. Eliminar as produções unitárias Da forma A B para as variáveis A e B 3. Eliminar símbolos inúteis: Variáveis ou terminais que não aparecem em nenhuma derivação a partir do símbolo de início da gramática. 1. ELIMINAÇÃO DE PRODUÇÕES VAZIAS ELIMINAÇÃO DE PRODUÇÕES VAZIAS Apesar de serem convenientes no projeto de gramáticas, as -produções não são essenciais. Note, no entanto, que sem uma produção que tenha ε no seu corpo, é impossível gerar o string vazio como elemento da linguagem. Assim, se L tem uma GLC, então L – {ε} tem uma GLC sem ε-produções. ELIMINAÇÃO DE PRODUÇÕES VAZIAS O primeiro passo do procedimento é a identificação de variáveis anuláveis. Uma variável A é anulável se A ⇒* ε. Se A é anulável, sempre que A aparecer em uma produção B → CAD, A poderá (ou não) derivar ε. Criamos duas versões da produção. Uma sem A no corpo, B → CD, que corresponde ao caso onde A seria usado para derivar ε. E outra ainda com A presente B → CAD, porém, não permitiremos que A derive ε retirando a produção A → ε da gramática. ELIMINAÇÃO DE PRODUÇÕES VAZIAS Seja G = (V, T, P, S) uma GLC. Os símbolos anuláveis são encontrados segundo o algoritmo recursivo a seguir: Base: se A → ε é uma produção de G então A é anulável; Indução: Se existe uma produção B → C1C2...CK onde cada Ci é anulável, então B é anulável. Só precisamos analisar casos onde o corpo das regras contém somente variáveis no passo indutivo. TEOREMA 7.7 Em qualquer gramática G, os únicos símbolos anuláveis são as variáveis encontradas pelo algoritmo anterior. ELIMINAÇÃO DE PRODUÇÕES VAZIAS A construção da gramática G1, sem ε-produções para G = (V, T, P, S) é obtida por: 1. Identificação de todos os símbolos anuláveis de G; 2. Construção da nova gramática G1 = (V, T, P1, S), onde P1 é dado por: Para cada produção A→X1X2...XK de P com k ≥ 1 suponha que m dos k valores Xi sejam anuláveis; A nova gramática terá 2m versões dessa produção, onde os Xi’s anuláveis, em todas as combinações possíveis estão presentes ou ausentes; Se m = k, não incluímos o caso no qual todos os Xi’s estão ausentes, pois P1 não terá produções do tipo A → ε. EXEMPLO Considere a gramática: S →AB A → aAA | ε B → bBB | ε A e B são diretamente anuláveis. Em seguida, S é anulável, pois na produção S →AB ambos os símbolos do corpo são anuláveis. EXEMPLO As produções da nova gramática são dadas como segue: Para o caso S→AB, há quatro maneiras de combinar as variáveis, porém todos os símbolos são anuláveis, então temos: S→AB | A| B Para a produção A→aAA, a segunda e terceira posições contém símbolos anuláveis, então temos quatro combinações: A→aAA | aA | aA| a De modo semelhante, obtemos: B→bBB | bB | b Resultado: L(G1) = L(G) – {}. TEOREMA 7.9 Se a gramática G1 é construída a partir de G pelo método anterior de eliminação de produções vazias, então L(G1) = L(G) – {ε}. 2. ELIMINAÇÃO DE PRODUÇÕES UNITÁRIAS ELIMINAÇÃO DE PRODUÇÕES UNITÁRIAS Uma produção unitária tem a forma A → B onde tanto A quanto B são variáveis. Tais produções são úteis principalmente na resolução de ambigüidades. Porém, elas podem complicar certas provas, e introduzem etapas de derivação extras que tecnicamente são desnecessárias. EXEMPLO O uso das produções unitárias E → T e T → F permitiu criar uma gramática não ambígua para expressões aritméticas: I → a | b | Ia | Ib | I0 | I1 F → I | (E) T→ F | T * F E → T | E + T Poderíamos expandir o T em E → T por uma de suas formas possíveis: Obtendo E → F | T * F, em seguida expandimos F, gerando E→ I | (E) | T * F Por último, expandimos I, tendo como resultado: E → a | b | Ia | Ib | I0 | I1 | (E) | T * F ELIMINAÇÃO DE PRODUÇÕES UNITÁRIAS A técnica sugerida no exemplo não funciona em todos os casos. Ela pode falhar se houver ciclos de produções unitárias: A → B, B → C, C → A A técnica que usaremos primeiro identifica todos os pares de variáveis A e B tais que A ⇒* B usando somente uma seqüência de produções unitárias. É possível que A ⇒* B sem que produções unitárias estejam envolvidas, por exemplo : A → BC, C → ε ELIMINAÇÃO DE PRODUÇÕES UNITÁRIAS Uma vez identificados tais pares, podemos substituir quaisquer seqüências de etapas de derivação em que: A ⇒ B1 ⇒ B2 ⇒ ... ⇒ Bn ⇒ α por uma produção que utilize a regra não unitária Bn → α diretamente a partir de A. Ou seja, A → α CONSTRUÇÃO DOS PARES UNITÁRIOS A definição recursiva que computa os pares (A, B) tais que A ⇒* B usando somente uma seqüência de produções unitárias é: Base: (A,A) é um par unitário para qualquer variável A. Isto é A ⇒* A em zero etapas. Indução: suponha que (A,B) seja um par unitário, e que B → C seja uma produção onde C é uma variável. Então (A, C) é um par unitário. EXEMPLO Considere a gramática: I → a | b | Ia | Ib | I0 | I1 F → I | (E) T→ F | T * F E → T | E + T A base nos dá os pares unitários (E,E), (T,T), (F,F) e (I,I). Para a etapa indutiva, podemos fazer as inferências De (E, E) e de E → T temos o novo par unitário (E , T). De (E, T) e de T → F temos o novo par unitário (E , F). De (E, F) e de F → I temos o novo par unitário (E , I). De (T, T) e de T → F temos o novo par unitário (T , F). De (T, F) e de F → I temos o novo par unitário (T , I). De (F, F) e de F → I temos o novo par unitário (F , I). TEOREMA 7.11 O algoritmo anterior encontra exatamente os pares unitários para uma GLC G. ELIMINAÇÃO DE PRODUÇÕES UNITÁRIAS Dada uma GLC G =(V, T, P, S), construímos a GLC G1=(V, T, P1, S) da seguinte maneira: 1. Encontramos todos os pares unitários de G; 2. Para cada par unitário (A, B), adicionamos a P1 todas as produções A → α onde B → α é uma produção não unitária em P; Observe que A = B é possível, desse modo P1 contém as produções não unitárias em P. EXEMPLO Continuando do exemplo anterior, a figura a seguir resume a etapa 2 do algoritmo anterior: I → a | b | Ia | Ib | I0 | I1 F → I | (E) T→ F | T * F E → T | E + T (E,E) E → E + T (E,T) E → T * F (E,F) E→ (E) (E,I) E → a | b | Ia | Ib | I0 | I1 (T,T) T → T * F (T,F) T → (E) (T,I) T → a | b | Ia | Ib | I0 | I1 (F,F) F → (E) (F,I) F → a | b | Ia | Ib | I0 | I1 (I,I) I → a | b | Ia | Ib | I0 | I1 •De (E, E) e de E → T temos o novo par unitário (E , T). •De (E, T) e de T → F temos o novo par unitário (E , F). •De (E, F) e de F → I temos o novo par unitário (E , I). •De (T, T) e de T → F temos o novo par unitário (T , F). •De (T, F) e de F → I temos o novo par unitário (T , I). •De (F, F) e de F → I temos o novo par unitário (F , I). 3. ELIMINAÇÃO DOS SÍMBOLOS INÚTEIS ELIMINAÇÃO DOS SÍMBOLOS INÚTEIS Um símbolo X é útil para a gramática G = (V, T, P, S) se existe alguma derivação: S ⇒* αXβ ⇒* w, onde w ∈ T*; Observe que X pode estar em V ou T; A forma sentencial αXβ poderia ser a primeira ou a última derivação. A retirada de símbolos inúteis evidentemente não altera a linguagem gerada. ELIMINAÇÃO DOS SÍMBOLOS INÚTEIS Identificamos as duas ações que um símbolo tem que realizar para ser útil: 1. Se X ⇒* w para algum string de terminais w, então dizemos que X é gerador. Todo terminal é gerador, pois ele deriva a si mesmo em zero etapas. 2. Se existe uma derivação S ⇒* αXβ para algum α e β,dizemos que X é alcançável. Um símbolo útil será ao mesmo tempo gerador e alcançável. Se eliminarmos os símbolos que não são geradores e os que não são alcançáveis, teremos somente os úteis. EXEMPLO Considere a gramática: S AB | a A b Todos os símbolos, com exceção de B, são geradores: a e b geram a si mesmos; S gera a e A gera b. Se eliminarmos B, devemos eliminar a produção S AB, obtendo: S a A b EXEMPLO Agora temos que apenas S e a são alcançáveis a partir de S. A eliminação de A e b nos deixa apenas a produção S a. Essa produção é por si só uma gramática que gera a linguagem {a}, da mesma forma que a gramática original. Observe que se começarmos pela verificação da alcançabilidade, veremos que todos os símbolos são alcançáveis, e só removeríamos B, que não é gerador, e ficaríamos ainda com símbolos inúteis. S a A b CÁLCULO DOS SÍMBOLOS GERADORES E ALCANÇÁVEIS Seja G=(V, T, P, S) uma gramática. Para calcular seus símbolos geradores usamos a seguinte indução: Base Todo símbolo de T é gerador; Indução Suponha que existe uma produção A → α, e todo símbolo de α já seja conhecido como gerador. Então A é gerador; A regra inclui o caso α = ε. CÁLCULO DOS SÍMBOLOS GERADORES E ALCANÇÁVEIS Seja G=(V, T, P, S) uma gramática, para calcular seus símbolos alcançáveis usamos a seguinte indução: Base S é alcançável; Indução Suponha que alguma variável A é alcançável. Então, para todas as produções com A na cabeça, os símbolos dos corpos dessas produções também são alcançáveis. RESUMO As simplificações vistas até aqui permitem converter uma GLC em uma GLC equivalente que: Não tem símbolos inúteis; Não tem ε-produções; Não tem produções unitárias. Uma ordem segura de aplicação dessas transformações é: 1. Eliminar ε-produções; 2. Eliminar produções unitárias; 3. Eliminar símbolos inúteis.
Compartilhar