Buscar

Propriedades das Linguagens Livres de Contexto - Parte I

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 31 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 31 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 31 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

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.

Outros materiais