Lema do Bombeamento Linguagens Livres de Contexto

  • View
    108

  • Download
    3

Embed Size (px)

Text of Lema do Bombeamento Linguagens Livres de Contexto

  • Slide 1
  • Lema do Bombeamento Linguagens Livres de Contexto
  • Slide 2
  • Agenda Lema do Bombeamento para CFLs Motivao Teorema Prova Exemplos de provas usando o lema
  • Slide 3
  • Bombeando FAs Strings de comprimento 3 ou mais no DFA acima podem ser bombeados, pois tais strings correspondem a caminhos de comprimento 3, e portanto visitam 4 vrtices. O princpio da Casa dos Pombos guarante ento que algum vrtice visitado mais de uma vez, resultando em um ciclo de bombeamento. 0 1 0 0 1 1 xy z
  • Slide 4
  • Bombeando PDAs Entretanto, o lema de bombeamento para linguagem regular falha nesse exemplo. Q: D um examplo de string que no pode ser bombeado. r s $ q $ X
  • Slide 5
  • Bombeando PDAs R: ( n ) n no pode ser bombeado na primeira metade. Entretanto, poderamos bombear dois substrings de uma vez. I.e. tomar k parenteses da esquerda e k da direita. r s $ q $ X
  • Slide 6
  • Bombeamento Duplo DEF: Um string s em L dito duplamente bombevel se podemos dividir s em s = uvxyz de modo que para todo i 0 temos que s = uv i xy i z L sendo pelo menos um de v,y no vazio. Q1: 00111 duplamente bombevel em 0*111? Q2: 00100 duplamente bombevel em {0 n 10 n }? Q3: 00100100 duplamente bombevel em {0 n 10 n 10 n } ?
  • Slide 7
  • Bombeamento Duplo R1: Sim. Todo string bombevel tambm duplamente bombevel, fazendo-se y =. Neste caso, tomamos u =, v = 00, x = y = z = 111. uv i xy i z =(00) i 111 est de fato em 0*111. R2: Sim. Faa u =, v = 00, x = 1, y = 11 e z = uv i xy i z =(00) i 1(00) i est de fato em {0 n 10 n } R3: NO! Bombeando duplamente 00100100 ou leva a excesso de 1s, ou aumenta 2 das sequncias de 0s, sem aumantar a sequncia de 0s restante.
  • Slide 8
  • Bombeamento Duplo Em geral, como bombeamento implica bombeamento duplo, toda linguagem regular (infinita) duplamente bombevel. Tambm verdade que toda linguagem livre de contexto (infinita) duplamente bombevel. Mas Q3 pode ser generalizada de modo a mostrar que {0 n 10 n 10 n } no admite bombeamento duplo para strings com comprimento maior do que um determinado. Isso termina provando que {0 n 10 n 10 n } no livre de contexto:
  • Slide 9
  • Lema do Bombeamento Livre de Contexto THM: Dada uma linguagem livre de contexto L, existe um nmero p (no. de bombeamento duplo) tal que todo string em L de comprimento p duplamente bombevel dentro de um substring de comprimento p. Em outras palavras, para todo s L com |s| p podemos escrever : s = uvxyz |vy | 1(partes bombevei no vazias) |vxy | p (bombeamento dentro da poro p) uv i xy i z L for all i 0 (bombea v e y)
  • Slide 10
  • CFPL Intuio Intuitivamente s = uvxyz encontrado do seguinte modo: Apenas um nmero finito de mudaas na pilha podem ocorrer em um ciclo do grafo de comprimento n (o nmero de estado). Portanto, se s suficient. longo, existiro estados q,r tais que o mesmo string empilhado em q desemplihado em r e tais que o caminho de q a r comea e termina com a mesma configurao de pilha. Com essa hiptese, podemos bombear juntos v e y j que v empilha o que y desempilha q r -x p s -v -y -z -u t k t 2 t 1 s k s 2 s 1
  • Slide 11
  • CFPL - Prova O que foi mostrado anteriormente possa ser formalizado para provar o Lema do Bombeamento para linguagens livres de contexto. Entrtanto a prova muito mais complicada do que a prova formal baseada em gramtica: Prova do CFPL: Seja L uma linguagem livre de contexto. Considere uma rvore de derivao de um string de L na qual algum nodo de varivel tem ele prprio como ancestral:
  • Slide 12
  • CFPL Prova Podemos substituir a ltima ocorrncia de A pela primeira. I.e., substituir na rvore A * and a por A * chuga and a choo Obtendo o seguinte: chuga foryou S aA A andachoo
  • Slide 13
  • chuga foryou S aA choo chuga A A andachoo E novamente: CFPL Prova
  • Slide 14
  • chuga foryou S aA choo chuga A choo chuga A A andachoo
  • Slide 15
  • Ou podemos substituir A * chuga and a choo por A * and a obtendo o resultado a seguir: chuga foryou S aA A andachoo
  • Slide 16
  • CFPL Prova No nosso caso particular, podemos criar qualquer string da forma a (chuga) i and a (choo) i for you foryou S aA anda
  • Slide 17
  • CFPL Prova De modo geral, qualquer caminho na rvore de derivao que tenha uma varvel repetida d origem a strings da forma uv i xy i z, todos em L. O restante da prova apenas um argumento de contagem que garante a ocorrncia de uma varivel repetida.
  • Slide 18
  • CFPL Prova Q: Se n o nmero de variveis da gramtica, para qual altura da rvore se pode garantir que pelo menos uma varivel ocorre repetida? (Lembre-se: a altura da rvore trivial apenas a raiz 0)
  • Slide 19
  • CFPL Prova R: Se n o nmero de variveis da gramtica, qualquer subrvore de altura h = n+1 tre uma varivel repetida. Isso porque o nvel inferior de uma rvore de derivao composto de terminais, portanto altura n+1 (= n+2 nveis) garante n+1 nveis de variveis, em pelo menos um ramo da rvore. O princpio da casa dos pombos garante que alguma varivel ocorre 2 vezes!
  • Slide 20
  • CFPL Prova Q: Se a gramtica est na Forma Normal de Chomsky, de que tipo qualquer rvore de derivao?
  • Slide 21
  • CFPL Prova R: Uma rvore binria! Q: Qual o nmero mximo de folhas que uma rvore binria de altura n pode ter?
  • Slide 22
  • CFPL Prova A: 2 n Q: Qual o nmero mximo de folhas que pode ter uma rvore de derivao de uma gramtica na Forma Normal de Chomsky, se a altura da rvore de derivao n+1?
  • Slide 23
  • CFPL Prova A: Tambm 2 n ! Isso porque a nica maneira de obter um terminal por uma regra da forma A a e, portanto, no h dois ramos no ltimo nvel. Q: Que comprimento de string garante que sua rvore de derivao tem altura n+1 ?
  • Slide 24
  • CFPL Prova R: 2 n. Isso porque nenhuma rvore com comprimento < n+1 poderia gerar essa quantidade de folhas, ou terminais. Isso nos leva a definir o nmero de bombeamento duplo como p=2 n. O resto do teorema segue das consideraes feitas previamente. Apenas precisamos verificar que o bombeamento pode ocorrer em um substring de comprimento p. Isso decorre de ocorrer uma varivel repetida nos ltimos n+2 nveis da rvore.
  • Slide 25
  • Provando que L no CFL Mtodo padro p/ aplicar o lema do bombeamento Apenas no. 3 muda de exemplo p/ exemplo: 1. Suponha que a linguagem livre de contexto. 2. Ento existe um no. de bombeamento p. 3. Encontre um string s que no seja duplamente bombevel, em um substring de comprimento p 4. 2 e 3 se contradizem, portanto, 1 deve ser falso e a linguagem no livre de contexto.
  • Slide 26
  • Provando que L no CFL Exemplo 1 L ={ 1 n 0 n 1 n 0 n | n 0 }
  • Slide 27
  • Provando que L no CFL Exemplo 1 A parte difcil a nmero 3!!! Tente s = 1 p 0 p 1 p 0 p Existem 3 casos onde a janela de viso vxy poderia estar.
  • Slide 28
  • Provando que L no CFL Exemplo 1 Caso I. Bombear p/ baixo (ou p/ cima) modificaria o no. de 0s e/ou o no. de 1s na primeira metado do string, sem alterar a segunda metade. Isso viola a definio da language.
  • Slide 29
  • Provando que L no CFL Exemplo 1 Casos II e III. Mesmo argumento do Caso I. (Caso III causaria mudana na segunda metade sem alterar a primeira. Caso II causaria mudaa na parte do meio, sem alterar os primeiros 1 p ou os ltimos.) Isso completa a prova.
  • Slide 30
  • Provando que L no CFL Exemplo 2 ADD = { x=y+z | x, y, e z so bit- strings que satisfazem a equao }
  • Slide 31
  • Provando que L no CFL Exemplo 1 A parte defcil a nmero 3! Seja s: 1 p+1 =1 p +10 p Existem duas posies onde o substring vxy pode ocorrer. (Janela-p)
  • Slide 32
  • Provando que L no CFL Exemplo 1 Caso I. v deve ocurrer esq. de = enquanto y deve ocorrer dir. j que, caso contrrio, o bombeamento resultaria em excesso de smbolos =, ou afetaria um lado da equao mas no o outro. Seja k o comprimento de v e l o comprimento de y. Bombeando p/ cima obtemos a suposta equao: 1 p+1-k =1 p-l +10 p. A equao no vlida porque o lado direito muito maior do que o lado esquerdo.
  • Slide 33
  • Provando que L no CFL Exemplo 1 Caso II. O bombeamento deve ocorrer direita de =: O lado direito afetado sem que haja alterao do lado esquerdo. Isso no mantm a propriedade de que o string satisfaz a equao. Isso conclui a prova de que a linguagem ADD no livre de contexto.
  • Slide 34
  • Exerccios {1 n | n primo} {0 n 1 n 0 n 1 n } {int x; x = 3; | x um string alfabtico} Portanto, dizer que Java livre de contexto no exato. (Se x = 3 ocorre, x deve ser previamente declarado!)