AULA 13 - PROPRIEDADES DE CFL'S (CAPITULO 8) ============================================ Lema de bombeamento (Pumping Lemma) para CFL's ---------------------------------------------- Seja L uma linguagem livre de contexto. Entao existe uma constante k, tal que para toda palavra z pertencente a L com |z| >= k existem u, v, w, x, y tal que: 1) z = uvwxy 2) |vwx| <= k 3) |vx| >= 1 4) u v^i w x^i y pertence a L para todo i >= 0 Prova: Seja G uma gramática que gera L na forma normal de Chomsky Primeira observacao: seja w uma palavra em L e A a arvore de derivacao de w. e n o tamanho do maior caminho da raiz a uma folha em A. Entao |w| <= 2^{n-1}. - por inducao no tamanho do maior caminho: base: S S | | n = 1 a epsilon |w| <= 2^{n-1} = 1 passo da inducao: S / \ T1 T2 Se em T1 e T2 nao ha' caminho maior que n-1, entao T1 em T1 e T2 a palavra tem tamanho <= 2^{n-2}. Entao a partir de S, o tamanho da palavra e' no maximo 2 * 2^{n-2} = 2^{n-1}. Para a segunda parte, utilizar como exemplo a gramatica: A -> BC B -> BA C -> AB A -> a B -> b E a derivacao da palavra bbabac - considere k = 2^n, onde n e' o numero de nao terminais em G. Se a palavra z em L tem |z| >= k, entao pela observacao acima, existe algum caminho de tamanho no minimo n+1 na arvore de derivacao de z (do contrario, nao seria possivel gerar uma palavra de tamanho >= 2^n, segundo a observacao acima). Em um caminho de tamanho n+1 existem n+2 vertices: 1 2 n n+1 O---O---O .... O----O----O 1 2 3 n n+1 n+2 Na arvore de derivacao todos os vertices exceto o ultimo sao nao terminais. Portanto, como so' existem n nao terminais na gramatica, algum nao terminal no caminho e' repetido. Mais especificamente, seguindo o caminho mais longo, da folha em direcao a raiz, encontraremos dois vertices v1 e v2 com o mesmo nao terminal. Considerando que v1 e' o vertice mais proximo da raiz, entre v1 e a folha so' podem existir no maximo n+2 vertices (do contrario, existem outros vertices dentre os n+2 com o mesmo nao terminal), ou seja, caminho de tamanho n+1. Portanto, a subarvore com raiz em v1 gera um string z1 (substring de z) de tamanho no maximo 2^n, ou seja k (dai' a condicao 2 do lema de que |vwx| <= k). Chame de z2 o string gerado pela subarvore com raiz em v2. Entao podemos escrever z1 = z3 z2 z4. Note que z3 e z4 nao podem ser ambos igual a epsilon, ja' que a primeira producao usada para a geracao de z1 deve ser da forma A -> BC (z2 e' gerada inteiramento na subarvore com raiz em B ou C; o outro nao terminal tem que necessariamente gerar algum terminal, ja' que G esta' na F.N. Chomsky). Dai' resulta a condicao (3) do lema que |vx| > 0. Entao: A =>* z3 A z4 e A=>* z2, onde |z3 z2 z4| <= 2^n = k Concluimos que A=>* z3^i z2 z4^i , para todo i >= 0. Utilizacao do Pumping Lemma --------------------------- 1) provar que L = {a^i b^i c^i | i >= 0} nao e' livre de contexto. Suponha que L seja L.C e k a constante do P.L. Considere a palavra z = a^k b^k c^k. Como |z| >= k, o lema diz que existem u,v,w,x,y tal que: 1) z=uvwxy 2) |vwx| <= k 3) |vx|>0 4) para todo i>= 0 uv^i w x^i y pertence a L. Como |vwx| <= k, nao e' possivel que v e x contenham a's e c's ja' que eles estao separados por k b's. Caso 1: v e x contem somente a's: para i = 0, u v^0 w x^0 y= uwy contem menos a's que b's e c's ja' que |vx| > 0, portanto nao pertence a L Caso 2: v e x contem somente b's: analogo ao caso 1 Caso 3: v e x contem somente c's: analogo ao caso 1 Caso 4: v e x contem a's e b's: para i=0, uwy contem menos a's e b's que c's e portanto nao pertence a L. Caso 5: v e x contem b's e c's: para i=0 uwy contem menos b's e c's que a's e portanto nao pertence a L. Em todos os casos possiveis encontramos um i tal que uv^i w x^i y nao pertence a L, o que contraria o P.L. Logo, podemos concluir que L nao e' livre de contexto. 2) provar que L = {0^n | n e' primo} nao e' livre de contexto. Suponha que L seja L.C. Seja k a constante do P.L. e z=0^n, onde n e' um numero primo maior que k. Segundo o lema, existem u,v,w,x,y tal que: 1) z=uvwxy 2) |vwx| <= k 3) |vx|>0 4) para todo i>= 0 uv^i w x^i y pertence a L. Para provar que L nao e' livre de contexto precisamos encontrar um valor de i tal que O^{n + (i-1)|vx|} nao seja primo. Para isto, basta fazer i=n+1. n + (n+1-1)|vx| = n + n * |vx| = n * (1 + |vx|) Como |vx| > 0, este numero nao e' primo, contrariando o P.L. Logo, concluimos que L nao e' livre de contexto. PROPRIEDADES DE FECHAMENTO -------------------------- 1) As CFLs sao fechadas sob concatenacao, uniao e estrela Kleene. Seja G1 = (V1, Sigma1, P1, S1) uma gramatica que gera L1 G2 = (V2, Sigma2, P2, S2) uma gramatica que gera L2 L1.L2 e' gerada pela gramatica: G3 = (V1 U V2 U {S3}, Sigma1 U Sigma2, P1 U P2 U {S3 -> S1 S2}, S3) L2 U L2 e' gerada pela gramatica: G4 = (V1 U V2 U {S4}, Sigma1 U Sigma2, P1 U P2 U {S4 -> S1 | S2}, S4) L1* e' gerada pela gramatica: G5 = (V1 U {S5}, Sigma1, P1 U {S5 -> S1 S5 | epsilon}, S5) Exemplo: A -> AB | a S -> aSb | epsilon B -> bB | b 2) As CFLs nao sao fechadas sob intersecao e complementacao: Contra-exemplo: L1 = {a^i b^i c^j | i,j >= 0} L2 = {a^j b^i c^i | i,j >= 0} L1 intersecao L2 = {a^i b^i c^i | i >= 0} que ja' provamos nao ser livre de contexto. Complementacao: Sejam L1 e L2 CFLs. Se CFLs sao fechados sob complemento, entao ------- -- -- L = L1 U L2 tambem e' livre de contexto. Mas L = L1 intersecao L2, que ja' provamos nao ser livre de contexto. Portanto, a suposicao inicial de que CFLs sao fechados sob complementacao e' falsa. 3) Seja R uma linguagem regular e L uma linguagem livre de contexto. Entao R intersecao L e' livre de contexto. Prova: construcao de um PDA que aceita a linguagem. Seja M1 = (Q1, Sigma1, Gama, delta1, q1, F1) um PDA que aceita L e M2 = (Q2, Sigma2, delta2, q2, F2) um DFA que aceita R. Construir um PDA M = (Q1xQ2, Sigma1 intersecao Sigma2, Gama, delta, [q1,q2], F1xF2), onde delta([e1,e2],a,A) contem ([e1',e2'],Y) se delta1(e1,a,A) contem (e1',Y) e delta2(e2,a) = e2' delta([e1,e2],epsilon,A) contem ([e1',e2],Y) se delta1(e1,epsilon,A) contem (e1',Y) Exemplo: L1 = {w em {a,b}* | #a's = #b's} L2 = a* b* Utilizacao de propriedades de fechamento: 1) facilitar construcao de gramaticas 2) provar que uma linguagem nao e' livre de contexto Ex: provar que L={w em {a,b,c}* | #a's = #b's = #c's} Se L e' livre de contexto, entao L intersecao a*b*c* tbem. deve ser. Mas, L intersecao a*b*c* = {a^i b^i c^i | i >=0} que ja' provamos nao ser livre de contexto.