Lema do Bombeamento – Gramticas Livres do Contexto

  • View
    46

  • Download
    0

Embed Size (px)

DESCRIPTION

Lema do Bombeamento – Gramáticas Livres do Contexto. Programa de Pós-Graduação em Ciência da Computação Profa. Sandra de Amo. Forma Normal de Chomsky. Toda gramática livre do contexto é equivalente a uma gramática onde as regras são do tipo: A  BC ou A  a - PowerPoint PPT Presentation

Text of Lema do Bombeamento – Gramticas Livres do Contexto

  • Lema do Bombeamento Gramticas Livres do ContextoPrograma de Ps-Graduao em Cincia da ComputaoProfa. Sandra de Amo

  • Forma Normal de ChomskyToda gramtica livre do contexto equivalente a uma gramtica onde as regras so do tipo:

    A BC ou A a

    Observao: frequentemente suporemos que a gramtica est na forma normal de Chomsky

  • Relao entre tamanho da palavra e tamanho da derivao Se |w| = n ento o tamanho da derivao de w 2n-1|w| = 1S w = aa Prova : Por induo sobre n Base da induo1 regra aplicada

    Tamanho da derivao = 1

    2. 1 1 = 1

    Logo : Tamanho da derivao = 2n-1

  • Hiptese de InduoSuponhamos que para toda palavra de comprimento k o tamanho de uma derivao 2k-1 Seja w uma palavra de comprimento k+1. No exemplo: w=aba...c b

    a b a c Construimos uma outraGramtica G substituindo a regraC AB por C c

    A palavra u= aba....c gerada por G e tem comprimento k, j que |w| = k+1

    Pela Hiptese de Induo : tamanho da derivao de u = 2k 1

    Tamanho da derivao de w =2k 1 + 2 = 2(k+1) 1 Cc

  • Caminhos na rvore de derivaoCaminho = S A1 A2 - ... An onde S, A1,...,An so variveis (ns internos)cada A1 filho de S e cada Ai filho de Ai-1 SA1BA2abbc

  • Quando um caminho contm variveis repetidas ? Seja K = Nmero de variveis da gramtica.

    Se o caminho tem tamanho maior ou igual a K ento com certeza contm variveis repetidas

  • Quando um caminho da raiz at o nvel logo acima de uma folha contm variveis repetidas ?CAAcSAACcaaSBBACaacK = 4CS -> ABS->a A-> ACA -> aB-> ACC -> cC-> SBVariveis repetidas 12345

  • Qual a relao entre o tamanho da palavra gerada e o tamanho mximo dos caminhos da rvore de derivao ?

    Teorema :

    Se todos os caminhos tm comprimento n ento a palavra derivada tem comprimento 2n-1Tamanho do maior caminho = Nmero de nveis da rvore de derivao

    Se nmero de nveis = n ento :

    Nmero mximo de elementos na ltima camada = 2n-1

    Nivel 1Nivel 2 Nivel n-1Nivel n-2Nivel n

  • Consequentemente :

    Se a palavra derivada tem comprimento > 2n-1ento existe um caminho de comprimento > n Portanto: Seja K = Nmero de variveis da gramtica

    Se a palavra derivada tem comprimento > 2K-1ento existe um caminho de comprimento > K

    Se um caminho tem tamanho > K ento com certeza contmvariveis repetidas.

  • Como detectar se uma linguagem no livre do contexto ?SAuvx y x y Bombeamento da subrvore v w x no primeiro n A (de baixo para cima), obtendo a palavra u v v w x x y

  • S -> ABS->a A-> ACA -> aB-> ACC -> cC-> ABz = a c a a a a a c cCAcSAACCcaaABBACacK = nmero de variveis da gram. = 4|z| = 9 > 24-1 = 8 ABaACaaA

  • CSAACaaSBBACcABACaaSBASBACACacacca c a a a a a c ca c a a a a a a a c a a c ca c a a a a a a a a a c a a c a a c caaCaSBAABAABACACacaaaCuvwxyz =uvvwxxyuvvvwxxxy

  • Como detectar se uma linguagem nao livre do contexto ?Se L livre do contexto ento

    Existe n > 0 (n > 2K-1, K = nmero de variveis da gramtica que gera L) tal que

    Para toda palavra z em L com |z| > n

    Existe uma maneira de dividir z em 5 partes z = u v w x y Para todo i 0 u vi w xi y pertence a L

  • Restrio na quebra em 5 Se |z| > n = 2k-1 ento existe maneira de dividir z em 5 partes : z = u v w x y tal que : |v w x| nProva: Se |z| = n > 2k-1 ento existe caminho de comprimento > kConsideremos um destes caminhosSubimos k+1 ns a partir do ltimo nCom certeza encontramos no caminho 2 ns com a mesma varivel AConsidere o n contendo a segunda ocorrncia da varivel A e pegue a subrvore SA com raiz neste n.Este vai ser o n que nortear a diviso de Z em 5 partes.A palavra gerada pela subrvore SA z = v w x Altura de SA k +1 Logo |z| 2k n

  • Altura > k AA

  • Subrvore SAAltura > k AAAltura de SA k+1Palavra derivada por SA tem comprimento 2k n

  • Como detectar se uma linguagem nao livre do contexto ?Se o texto abaixo no verdadeiro ento L no livre do contexto

    Existe n > 0 (n = 2K-1, K = nmero de variveis da gramtica que gera L) tal que

    Para toda palavra z em L com |z| > n

    Existe uma maneira de dividir z em 5 partes z = u v w x y | vwx | n | vx | > 0 tal que (JUSTIFIQUE !!) Para todo i 0 u vi w xi y pertence a L

  • Logo, se a condio abaixo verificada ento L no livre do contexto

    Para todo n > 0

    Existe uma palavra z em L com |z| > n

    Para toda maneira de dividir z em 5 partes z= u v w x y | vwx | n | vx | > 0 tal que Existe i 0 u vi w xi y no pertence a L

  • Condio suficiente para L no ser livre do contextoPara todo n > 0

    Existe uma palavra z em L com |z| > n

    Para toda maneira de dividir z em 5 partes z = u v w x y | vwx | n | vx | > 0 tal que Existe i 0 u vi w xi y no pertence a L

  • ExemplosVimos que L = {0k1k | k 0 } no regular.Entretanto L livre do contexto L = L(G) S S 0 S 1

  • Exemplo Mostrar que {0k1k2k | k 0} no livre do contexto (no gerada por uma Gramtica LC)

    Seja n > 0Considere w = 000...0 111...1 22...2 = 0n1n2n

    Seja w = u v w y x com |vwy| n Ento necessariamente uma das possibilidades a seguir se verifica:vwy est contida no grupo de 0s. Neste caso quando bombeamos v e y obtemos uma palavra com mais 0s do que 1s ou 2s. vwy est contida no grupo de 2s. Anlogo a (1)vwy est contida no grupo de 1s. Anlogo a (1)v contm 0s e 1s: bombeando v obtemos uma palavra que no est na linguagem (conter 0s seguidos de 1s)v contm 1s e 2s: Anlogo a (4)

  • Linguagens RegularesLinguagens livres do contexto Linguagens Turing DecidveisTodas as linguagens

    *****************