Baixe o app para aproveitar ainda mais
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 i0, uviwxiy está em L. EXEMPLO L = {0m1m2m|m1} 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|n1} 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|n1} 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).
Compartilhar