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
• Observação: frequentemente suporemos que a
gramática está na forma normal de Chomsky
Relação entre tamanho da palavra
e tamanho da derivação
Se |w| = n então o tamanho da derivação de w é 2n-1
Prova : Por indução sobre n
S
Base da indução
a
|w| = 1
w=a
1 regra aplicada
Tamanho da derivação = 1
2. 1 – 1 = 1
Logo :
Tamanho da derivação
= 2n-1
Hipótese de Indução
Suponhamos que para toda palavra de comprimento k
o tamanho de uma derivação é 2k-1
Seja w uma palavra de comprimento k+1. No exemplo: w=aba...c b
Construimos uma outra
Gramática G’ substituindo a regra
C  AB por C c
A palavra u= aba....c é gerada por
G’ e tem comprimento k,
já que |w| = k+1
C
C
A
a
b
a
c
c B
b
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
Caminhos na árvore de derivação
Caminho = S – A1 – A2 - ... – An
onde S, A1,...,An são variáveis (nós internos)
cada A1 é filho de S e cada Ai é filho de Ai-1
S
A1
B
A2
a
b
b
c
Quando um caminho contém
variáveis repetidas ?
• Seja K = Número de variáveis da
gramática.
• Se o caminho tem tamanho maior ou igual
a K então com certeza contém variáveis
repetidas
Quando um caminho da raiz até o nível
logo acima de uma folha contém
variáveis repetidas ?
S
5
B
A
4
A
C
a
c
A
3
C
A
a
2
B
S
a
C
A
c
1
S -> AB
S->a
A-> AC
A -> a
B-> AC
C -> c
C-> SB
C
K=4
Variáveis repetidas
a
c
Qual a relação entre o tamanho da palavra
gerada e o tamanho máximo dos caminhos
da árvore de derivação ?
Teorema :
Se todos os caminhos têm comprimento ≤ n então
a palavra derivada tem comprimento ≤ 2n-1
Nivel 1
Nivel 2
Tamanho do maior caminho =
Número de níveis da árvore de derivação
Se número de níveis = n então :
Nivel n-2
Nivel n-1
Nivel n
Número máximo de elementos na
última camada = 2n-1
Consequentemente :
Se a palavra derivada tem comprimento > 2n-1
então existe um caminho de comprimento > n
Portanto: Seja K = Número de variáveis da gramática
Se a palavra derivada tem comprimento > 2K-1
então existe um caminho de comprimento > K
Se um caminho tem tamanho > K então com certeza contém
variáveis repetidas.
Como detectar se uma linguagem não
é livre do contexto ?
S
A
A
S
A
u
A
v
v
w
u
x
v
w
x
y
y
x
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
B
A
S -> AB
S->a
A-> AC
A -> a
B-> AC
C -> c
C-> AB
A
C
a
c
z=acaaaaacc
K = número de variáveis da gram. = 4
|z| = 9 > 24-1 = 8
A
C
A
C
c
B
A
a
a
A
C
B
A
a
A
a
a
C
c
S
A
A
a
z= acaaaaacc
u v w x
y
B
A
C
C
A
c
a
x
y
x
u v
v w
acaaaaaaaaacaacaac c
u v v v w x
y
x
x
c
BB
S
SA
a
acaaaaaaacaac c
C
S
A
a
C
C
A
a
B
AA
C
a
c
B
A
a
A
a
C
c
Como detectar se uma linguagem
nao é livre do contexto ?
• Se L é livre do contexto então
• Existe n > 0 (n > 2K-1, K = número de variáveis da
gramática que gera L) tal que
• Para toda palavra z em L com |z| > n
• Existe uma maneira de dividir z em 5 partes
•
–
z=uvwxy
Para todo i ≥ 0
– u vi w xi y pertence a L
Restrição “na quebra em 5”
Se |z| > n = 2k-1 então existe maneira de dividir z em 5 partes : z = u v w x y tal
que :
|v w x| ≤ n
Prova:
•
•
•
•
•
•
•
•
•
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
Altura de SA≤ k+1
Altura > k
A
A
Subárvore SA
Palavra derivada por SA tem comprimento ≤ 2k ≤ n
Como detectar se uma linguagem
nao é livre do contexto ?
• Se o texto abaixo não é verdadeiro então
L não é livre do contexto
• Existe n > 0 (n = 2K-1, K = número de variáveis da gramática que
gera L) tal que
• Para toda palavra z em L com |z| > n
• Existe uma maneira de dividir z em 5 partes
–
z=uvwxy
–
| vwx | ≤ n
–
| vx | > 0 tal que (JUSTIFIQUE !!)
• Para todo i ≥ 0
– u vi w xi y pertence a L
Logo, se a condição abaixo é
verificada então L não é 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 não pertence a L
Condição suficiente para L não ser
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=uvwxy
–
| vwx | ≤ n
–
| vx | > 0 tal que
Existe i ≥ 0
– u vi w xi y não pertence a L
Exemplos
• Vimos que L = {0k1k | k ≥ 0 } não é
regular.
• Entretanto L é livre do contexto
• L = L(G)
Sε
S0S1
Exemplo
Mostrar que {0k1k2k | k ≥ 0} não é livre do contexto (não é gerada por uma
Gramática LC)
Seja n > 0
Considere w = 000...0 111...1 22...2
= 0 n1 n2 n
Seja w = u v w y x com |vwy| ≤ n
1)
2)
3)
4)
5)
Então necessariamente uma das possibilidades a seguir se verifica:
vwy está contida no grupo de 0’s. Neste caso quando bombeamos v e y
obtemos uma palavra com mais 0’s do que 1’s ou 2’s.
vwy está contida no grupo de 2’s. Análogo a (1)
vwy está contida no grupo de 1’s. Análogo a (1)
v contém 0’s e 1’s: bombeando v obtemos uma palavra que não está na
linguagem (conterá 0’s seguidos de 1’s)
v contém 1’s e 2’s: Análogo a (4)
Todas as linguagens
Linguagens Turing Decidíveis
Linguagens livres do
contexto
Linguagens
Regulares