Lema do Bombeamento – Lema do Bombeamento – Gramáticas Livres do Gramáticas Livres do

ContextoContexto

Programa de Pós-Graduação Programa de Pós-Graduação em Ciência da Computaçãoem Ciência da Computação

Profa. Sandra de AmoProfa. Sandra de Amo

Forma Normal de ChomskyForma Normal de Chomsky

• Toda gramática livre do contexto é Toda gramática livre do contexto é equivalente a uma gramática onde as regras equivalente a uma gramática onde as regras são do tipo:são do tipo:

A A BC BC

ou ou

A A a a

• Observação:Observação: frequentemente suporemos que frequentemente suporemos que a gramática está na forma normal de Chomskya gramática está na forma normal de Chomsky

Relação entre tamanho da Relação entre tamanho da palavra e tamanho da palavra e tamanho da derivaçãoderivação

Se |w| = n então o tamanho da derivação de w é 2n-1

|w| = 1

S

w = a

a

Prova : Por indução sobre n

Base da indução

1 regra aplicada

Tamanho da derivação = 1

2. 1 – 1 = 1

Logo : Tamanho da derivação = 2n-1

Hipótese de InduçãoHipótese de InduçãoSuponhamos que para toda palavra de comprimento k Suponhamos que para toda palavra de comprimento k o tamanho de uma derivação é 2k-1 o tamanho de uma derivação é 2k-1

Seja w uma palavra de comprimento k+1. No exemplo: Seja w uma palavra de comprimento k+1. No exemplo: w=aba...c w=aba...c bb

a b a c

Construimos uma outraGramática 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 Hipótese de Indução : tamanho da derivação de u = 2k – 1

Tamanho da derivação de w =2k – 1 + 2 = 2(k+1) – 1 b b

BA

CC

c

Caminhos na árvore de Caminhos na árvore de derivaçãoderivação

CaminhoCaminho = S – A1 – A2 - ... – An = S – A1 – A2 - ... – An

onde S, A1,...,An são variáveis (nós internos)onde S, A1,...,An são variáveis (nós internos)

cada A1 é filho de S e cada Acada A1 é filho de S e cada Aii é filho de A é filho de Ai-1i-1

S

A1 B

A2

a b b c

Quando um caminho contém Quando um caminho contém variáveis repetidas ? variáveis repetidas ?

• Seja Seja KK = Número de variáveis da = Número de variáveis da gramática.gramática.

• Se o caminho tem tamanho maior ou Se o caminho tem tamanho maior ou igual a igual a KK então com certeza contém então com certeza contém variáveis repetidas variáveis repetidas

Quando um caminho da raiz até o Quando um caminho da raiz até o nível logo acima de uma folha nível logo acima de uma folha contém variáveis repetidas ?contém variáveis repetidas ?

CA

A c

S

A

A C

ca

aS B

B

A Ca

a c

K = 4

C

S -> ABS->a A-> ACA -> aB-> ACC -> cC-> SB

Variáveis repetidas

1

2

3

4

5

Qual a relação entre o tamanho da Qual a relação entre o tamanho da palavra gerada e o tamanho máximo palavra gerada e o tamanho máximo dos caminhos da árvore de dos caminhos da árvore de derivação ?derivação ?

Teorema :Teorema :

Se todos os caminhos têm comprimento ≤ n então a palavra derivada tem comprimento ≤ 2n-1

Tamanho do maior caminho = Número de níveis da árvore de derivação

Se número de níveis = n então :

Número máximo de elementos na última camada = 2n-1

Nivel 1

Nivel 2

Nivel n-1

Nivel n-2

Nivel n

Consequentemente :Consequentemente :

Se a palavra derivada tem comprimento > 2n-1

então existe um caminho de comprimento > n

Portanto:Portanto: Seja K = Número de variáveis da gramática Seja K = Número de variáveis da gramática

Se a palavra derivada tem comprimento > Se a palavra derivada tem comprimento > 2K-1

então existe um caminho de comprimento > existe um caminho de comprimento > KK

Se um caminho tem tamanho > K então com certeza contémSe um caminho tem tamanho > K então com certeza contémvariáveis repetidas. variáveis repetidas.

Como detectar se uma linguagem Como detectar se uma linguagem não é livre do contexto ?não é livre do contexto ?

S

A

A

u v w x y

S

A

u v x y A

v w x

x y

Bombeamento da subárvore 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-> AB

z = a c a a a a a c c

C

A c

S

A

A C

Cca

aA B

B

A Ca

c

K = número de variáveis da gram. = 4|z| = 9 > 24-1 = 8

A B

a A C

a

a

A

C

S

A

A C

a

aS B

B

A

C

c

A B

A C

aa

S B

A

S B

A C

A Ca

ca

cc

a c a a a a a c c

a c a a a a a a a c a a c c

a c a a a a a a a a a c a a c a a c c

a

a

C

aS B

A

A B

A

A B

A C

A Ca

ca

a

a

C

u

v

w x y

z =

u v

v

w x x y

u v v v w x x x y

Como detectar se uma Como detectar se uma linguagem nao é livre do linguagem nao é livre do contexto ?contexto ?• Se L Se L é livre do contextoé livre do contexto então então

• ExisteExiste n > 0 (n > 2 n > 0 (n > 2K-1K-1, K = número de variáveis , K = número de variáveis da gramática que gera L) tal queda gramática que gera L) tal que

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

• ExisteExiste uma maneira de dividir z em 5 partes uma maneira de dividir z em 5 partes– z = u z = u vv w w xx y y

• Para todoPara todo i ≥ 0 i ≥ 0– u u vvii w w xxii y pertence a L y pertence a L

Restrição Restrição ““na quebra em 5na quebra em 5”” Se |z| > n = 2Se |z| > n = 2k-1k-1 então existe maneira de dividir z em 5 partes : z = u v então existe maneira de dividir z em 5 partes : z = u v

w x y tal que : w x y tal que :

|v w x| ≤ nProva: • Se |z| = n > 2k-1 então existe caminho de comprimento > k• Consideremos um destes caminhos• Subimos k+1 nós a partir do último nó• Com certeza encontramos no caminho 2 nós com a mesma variável

A• Considere o nó contendo a segunda ocorrência da variável A e

pegue a subárvore SA

com raiz neste nó.• Este vai ser o nó que norteará a divisão de Z em 5 partes.• A palavra gerada pela subárvore SA é z’ = v w x • Altura de SA é ≤ k +1 • Logo |z’| ≤ 2k ≤ n

Altura > k

A

A

Subárvore SA

Altura > k

A

A

Altura de SA≤ k+1

Palavra derivada por SA tem comprimento ≤ 2k ≤ n

Como detectar se uma Como detectar se uma linguagem nao é livre do linguagem nao é livre do contexto ?contexto ?• Se o texto abaixo Se o texto abaixo não não é verdadeiroé verdadeiro então então L L não é livre do contextonão é livre do contexto

• ExisteExiste n > 0 (n = 2 n > 0 (n = 2K-1K-1, K = número de variáveis da , K = número de variáveis da gramática que gera L) tal quegramática que gera L) tal que

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

• ExisteExiste uma maneira de dividir z em 5 partes uma maneira de dividir z em 5 partes– z = u z = u vv w w xx y y – | vwx | ≤ n | vwx | ≤ n – | vx | | vx | >> 0 tal que 0 tal que (JUSTIFIQUE !!) (JUSTIFIQUE !!)

• Para todoPara todo i ≥ 0 i ≥ 0– u u vvii w w xxii y pertence a L y pertence a L

Logo, se a condição abaixo é Logo, se a condição abaixo é verificada então L verificada então L não é livre não é livre do contextodo contexto

• Para todoPara todo n > 0 n > 0

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

• Para todaPara toda maneira de dividir z em 5 partes maneira de dividir z em 5 partes– z= u z= u vv w w xx y y – | vwx | ≤ n | vwx | ≤ n – | vx | | vx | >> 0 tal que 0 tal que

• ExisteExiste i ≥ 0 i ≥ 0– u u vvii w w xxii y y nãonão pertence a L pertence a L

Condição suficiente para L não Condição suficiente para L não ser livre do contextoser livre do contexto• Para todoPara todo n > 0 n > 0

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

• Para todaPara toda maneira de dividir z em 5 partes maneira de dividir z em 5 partes– z = u z = u vv w w xx y y – | vwx | ≤ n | vwx | ≤ n – | vx | | vx | >> 0 tal que 0 tal que

• ExisteExiste i ≥ 0 i ≥ 0– u u vvii w w xxii y y nãonão pertence a L pertence a L

ExemplosExemplos

• Vimos que L = {0Vimos que L = {0kk11kk | k ≥ 0 } não é | k ≥ 0 } não é regular.regular.

• Entretanto L é livre do contexto Entretanto L é livre do contexto

• L = L(G)L = L(G)

S S εε

S S 0 S 1 0 S 1

Exemplo Exemplo Mostrar que {0Mostrar que {0kk11kk22kk | k ≥ 0} não é livre do contexto (não é gerada por | k ≥ 0} não é livre do contexto (não é gerada por

uma Gramática LC)uma Gramática LC)

Seja n > 0Seja n > 0

Considere w = 000...0 111...1 22...2 = 0Considere w = 000...0 111...1 22...2 = 0nn11nn22nn

Seja w = u v w y x com |vwy| ≤ n Seja w = u v w y x com |vwy| ≤ n

Então necessariamente uma das possibilidades a seguir se Então necessariamente uma das possibilidades a seguir se verifica:verifica:

• vwy está contida no grupo de 0vwy está contida no grupo de 0’’s. Neste caso quando bombeamos s. Neste caso quando bombeamos v e y obtemos uma palavra com mais 0v e y obtemos uma palavra com mais 0’’s do que 1s do que 1’’s ou 2s ou 2’’s. s.

• vwy está contida no grupo de 2vwy está contida no grupo de 2’’s. Análogo a (1)s. Análogo a (1)

• vwy está contida no grupo de 1vwy está contida no grupo de 1’’s. Análogo a (1)s. Análogo a (1)

• v contém 0v contém 0’’s e 1s e 1’’s: bombeando v obtemos uma palavra que não s: bombeando v obtemos uma palavra que não está na linguagem (conterá 0está na linguagem (conterá 0’’s seguidos de 1s seguidos de 1’’s)s)

• v contém 1v contém 1’’s e 2s e 2’’s: Análogo a (4)s: Análogo a (4)

Linguagens Regulares

Linguagens livres do contexto

Linguagens Turing Decidíveis

Todas as linguagens