Propriedades das Linguagens livres de contexto - Parte III

Prévia do material em texto

PROPRIEDADES DAS 
LINGUAGENS LIVRES DE 
CONTEXTO III 
Marcelo Guerra 
LEMA DO BOMBEAMENTO PARA LLC’S 
 Ferramenta para mostrar que uma linguagem não é 
livre de contexto. 
 
 Em qualquer string de uma GLC longo o suficiente, 
 é possível encontrar no máximo dois sub-strings curtos e 
próximos que podemos bombear em conjunto. 
 
 ou seja, podemos repetir ambos os strings i vezes, para 
qualquer i inteiro, e o string resultante ainda estará na 
linguagem. 
LEMA DO BOMBEAMENTO PARA LLC’S 
 Desmembramos cada string z na LLC em cinco partes e 
bombeamos a segunda e a quarta partes conjuntamente. 
 Teorema 7.18 (Lema do bombeamento para 
LLCs): 
 Seja L uma LLC. Então existe uma constante n tal 
que, se z é uma string em L tal que |z| é pelo menos 
n (|z|≥n), podemos escrever z = uvwxy sujeito às 
seguintes condições: 
1. |vwx| ≤ n, ou seja, a porção intermediária não é 
maior do que n; 
2. vx ≠ e são os fragmentos a serem bombeados. Note 
que pelo menos um deles não é vazio; 
3. Para todo i0, uviwxiy está em L. 
EXEMPLO 
 L = {0m1m2m|m1} 
 
 Se L for uma LLC, então existe um inteiro n dado pelo lema. 
 
|z| = m=3n 
 
 Escolhemos z = 0n1n2n. 
 
 Desmembramos z em uvwxy, onde |vwx| ≤ n e vx ≠ ε. 
 
 Assim, sabemos que vwx não pode envolver ao mesmo tempo 0’s 
e 2’s, pois o último 0 e o primeiro 2 estão separados por n+1 
posições. 
 
 Temos os seguintes casos: 
EXEMPLO 
1. vwx não tem nenhum 2, então vx consiste apenas em 
0’s e 1’s e tem pelo menos 1 desses símbolos. 
 Assim uwy, que teria de estar em L pelo lema do 
bombeamento, tem n 2’s, mas tem menos de n 0’s ou 1’s. 
 Concluímos que L não é livre de contexto. 
 
2. vwx não tem nenhum 0. 
 De modo semelhante, uwy tem n 0’s, mas tem um número 
menor de 1’s ou 2’s. 
 Portanto, não está em L. 
 
 Qualquer que seja o caso, pelo lema do bombeamento, 
mostramos que L não é uma LLC. 
 
Z=uvwxy 
EXEMPLO 
 L = {0n12n-1|n1} 
 
 Para n=3: 00011111 
 Z=uviwxiy 
 Z=uvwxy 
 00011111 
 Bombeando v e x para i=3, temos: 
 00000111111111 
 
 
PROPRIEDADES DE FECHAMENTO 
DAS LLC’S 
PROPRIEDADES DE FECHAMENTO 
 A família das LLCs é fechada em relação a: 
 
 União 
 Concatenação 
 Fecho-Estrela e Fecho-Positivo 
 Homomorfismos 
 Reversão 
UNIÃO 
 Suponha que temos duas gramáticas livres de contexto 
G1 = (V1, T1 , P1, S1) e G2 = (V2, T2 , P2, S2) onde V1 e 
V2 tem elementos diferentes. 
 Seja G = (V1  V2  {S}, T1  T2, P1  P2  { S  S1, 
S  S2}, S) 
 onde S é um novo símbolo não – terminal 
 Como as únicas regras que envolvem S são S  S1 e S  S2, 
então: 
 Se S  w, temos S1  w ou S2  w. 
 
 Isto equivale a dizer que se w  L(G) então w  L(G1)  
L(G2). 
UNIÃO 
CONCATENAÇÃO 
 ... com uma construção semelhante, obtemos 
L(G) = L(G1 )L(G2) gerada pela gramática: 
FECHO 
 Aqui, L(G1)* é gerada por: 
 
SUBSTITUIÇÕES 
 As linguagens livres de contexto são fechadas sob 
substituição. 
 
 A partir de uma linguagem livre de contexto, 
substituindo cada símbolo terminal a por uma 
linguagem livre de contexto La, obtemos a 
linguagem 
 
 
 
 que também é livre de contexto. 
 
 
 
 
}...|...{ 2121 iainn LweLaaawww 
SUBSTITUIÇÕES 
 Seja Σ um alfabeto, e para todo a ∈ Σ escolhemos uma 
linguagem livre de contexto La 
 As linguagens escolhidas podem estar sobre quaisquer 
alfabetos, não necessariamente Σ e não necessariamente 
iguais. 
 
 Essas escolhas definem uma função s (uma 
substituição) sobre Σ, 
 
 Nos referimos a La como s(a) para cada a 
SUBSTITUIÇÕES 
 Se w=a1a2...an ∈ Σ*, então s(w) é a linguagem de 
todos os strings x1x2...xn tais que o string xi está na 
linguagem s(ai) para i=1,2,...,n 
 s(w) é a concatenação das linguagens s(a1)s(a2)...s(an) 
 
 Exemplo: 
 Suponha que s(0) = {anbn|n1} e s(1) = {aa,bb}. 
 Ou seja, s é uma substituição sobre o alfabeto {0,1} 
 
 Seja w = 01, então s(w) é a concatenação das linguagens 
s(0)s(1) 
 s(w) consiste em todos os strings nas formas anbnaa e anbn+2 
onde n 1 
 
SUBSTITUIÇÕES 
 A aplicação de s a uma linguagem L, s(L) é definida pela união de 
s(w) para todos os strings w em L. 
 
 Exemplo: 
 Suponha que L=L(0*) 
 Conjunto de todas as strings de 0’s 
 
 Então s(L) = (s(0))*. Essa linguagem é o conjunto de todos os 
strings da forma 
 
an1bn1an2bn2...ankbnk 
 
 para algum k  0 e qualquer seqüência n1, n2,...nk de inteiros 
positivos 
 
 Exemplos de strings 
 ε, aabbaaabbb e abaabbabab 
TEOREMA 7.23 
 Se L é uma LLC sobre o alfabeto Σ e s é uma 
substituição em Σ tal que s(a) é uma LLC para 
cada a em Σ, então s(L) é uma LLC. 
 
 Prova (idéia) 
 Tomar uma GLC para L e construir a gramática para 
s(L) substituindo cada terminal a da primeira pelo 
símbolo inicial de uma LLC para a linguagem s(a). 
 O resultado é uma GLC que gera s(L). 
SUBSTITUIÇÕES - EXEMPLO 
HOMOMORFISMO 
 Suponha que L seja uma LLC sobre Σ e que h 
seja um homomorfismo em Σ. 
 
 Seja s a substituição que troca cada símbolo a 
em Σ pela linguagem que consiste no único 
string que consiste em h(a) 
 
 Isto é, s(a) = {h(a)} para todo a em Σ 
 
 Então h(L) = s(L) 
 
 
 
HOMOMORFISMO 
REVERSÃO 
 Reversão 
 Se L é uma LLC, então LR também o é. 
 
 
 
 
 
 
INTERSEÇÃO E COMPLEMENTO 
 As linguagens livres de contexto não são fechadas 
sob interseção ou complemento. 
INTERSEÇÃO E COMPLEMENTO 
 Interseção com uma linguagem regular: 
 Se L é uma LLC e R é uma linguagem regular, então 
L R é uma LLC. 
 
Teorema: 
 A interseção de uma linguagem livre de 
contexto com uma linguagem regular é 
uma linguagem livre de contexto. 
INTERSEÇÃO E COMPLEMENTO 
 Teorema 7.29: As afirmativas a seguir são 
verdadeiras a respeito das LLCs L, L1 e L2, e para 
uma linguagem regular R: 
 
1. L – R é uma LLC. 
2. não é necessariamente uma LLC. 
3. L1 – L2 não é necessariamente LLC. 
 
_
L
EXERCÍCIOS 
 Prove que L = {0i1j2i3j | i>=1 e j>=1} não é LLC. 
 
 Seja L = {ab, bb} e S a substituição dada por 
S(a) = 10* e S(b)= 00*. Defina S(L).