Mais Aplicações
do
Lema do Bombeamento
1
Lema do Bombeamento:
Para toda ling. livre de contexto infinita
existe um inteiro
m tal que
para todo string w  L,
podemos escrever
com
L
| w | m
w  uvxyz
| vxy | m and | vy | 1
e devemos ter:
i i
uv xy z  L,
for all i  0
2
Linguagens Não Livres de Contexto
{a b c : n  0}
n n n
{ww : w {a, b}}
Linguagens Livres de Contexto
{a b : n  0}
n n
{ww : w  {a, b}*}
R
3
Teorema: A linguagem
L  {ww : w {a, b}*}
não é livre de contexto
Prova:
Use o Lema do Bombeamento
para linguagens livres de contexto
4
L  {ww : w {a, b}*}
Suponha por contradição que
L
é livre de contexto
Como L é livre de contexto e infinita
podemos aplicar o lema do bombeamento
5
L  {ww : w {a, b}*}
O Lema do Bombeamento nos dá
um número magico m tal que:
Dado um string de
L com comprimento ³ m
tomamos: a
m m m m
b a b
L
6
L  {ww : w {a, b}*}
Podemos escrever:
com
| vxy | m e
a b a b  uvxyz
m m m m
| vy | 1
O Lema do Bombeamento diz:
uv xy z  L para todo i  0
i
i
7
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
| vxy | m
| vy | 1
Examinemos todas as possíveios localizações
do string vxy em a mb m a mb m
8
L  {ww : w {a, b}*}
| vxy | m
a b a b  uvxyz
m m m m
Caso 1:
va
vxy está nos primeiros a
k1
ya
k2
| vy | 1
m
k1  k2  1
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
z
u vx y
9
L  {ww : w {a, b}*}
| vxy | m
a b a b  uvxyz
m m m m
Caso 1:
va
vxy está nos primeiros a
k1
ya
k2
| vy | 1
m
k1  k2  1
m
m
m  k1  k2 m
a ................ a b ...... b a ...... a b ...... b
z
u v2 x y 2
10
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
Caso 1:
a
| vxy | m
vxy está nos primeiros a
m  k1  k2 m m m
| vy | 1
m
b a b  uv xy z  L
2
2
k1  k2  1
11
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
Case 1:
a
| vxy | m
| vy | 1
vxy está nos primeiros a
m  k1  k2 m m m
m
b a b  uv xy z  L
2
Estretando, do Lema do Bomb.:
Contradição!!!
2
uv xy z  L
2
2
12
L  {ww : w {a, b}*}
| vxy | m
a b a b  uvxyz
m m m m
| vy | 1
Caso 2: v está nos primeiros a m
y está nos primeiros b
va
k1
yb
k2
m
k1  k2  1
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
z
u v x y
13
L  {ww : w {a, b}*}
| vxy | m
a b a b  uvxyz
m m m m
| vy | 1
Caso 2: v está nos primeiros a m
y está nos primeiros b
va
k1
yb
k2
m
k1  k2  1
m
m
m  k2
m  k1
a ............ a b ............ b a ...... a b ...... b
2 x
2
z
u
v
y
14
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
| vxy | m
| vy | 1
Caso 2: v está nos primeiros a m
y está nos primeiros b
a
m  k1 m  k2 m m
b
m
a b  uv xy z  L
2
2
k1  k2  1
15
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
| vxy | m
| vy | 1
Case 2: v está nos primeiros a m
y
a
m
está nos primeiros b
m  k1 m  k2 m m
b
a b  uv xy z  L
2
However, from Pumping Lemma:
Contradição!!!
2
uv xy z  L
2
2
16
L  {ww : w {a, b}*}
| vxy | m
a b a b  uvxyz
m m m m
| vy | 1
Caso 3: v sobrepõe os primeiros a b
m m
y está nos primeiros b
v
k1 k 2
a b
yb
k3
m
k1, k2  1
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
u
v xy z
17
L  {ww : w {a, b}*}
| vxy | m
a b a b  uvxyz
m m m m
| vy | 1
Caso 3: v sobrepõe os primeiros a b
m m
y está nos primeiros b
v
k1 k 2
a b
yb
k3
m
k1, k2  1
k2
k1 m  k3
m
m
m
a ...... a b ... b a ... a b ......... b a ...... a b ...... b
2
2
u
z
x
v
y
18
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
| vxy | m
| vy | 1
Caso 3: v sobrepõe os primeiros a b
m m
y está nos primeiros b
m k2 k1 m  k3 m m
a b a b
a b
m
 uv xy z  L
2
2
k1, k2  1
19
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
| vxy | m
| vy | 1
Caso 3: v sobrepõe os primeiros a b
m m
y está nos primeiros b
m k2 k1 k3 m m
a b a b a b
m
 uv xy z  L
2
Entretanto, do Lema do Bomb.:
Contradição!!!
2
uv xy z  L
2
2
20
L  {ww : w {a, b}*}
a b a b  uvxyz
m m m m
| vxy | m
Case 4: v está nos primeiros a
| vy | 1
m
m m
y sobrepõe os primeiros a b
Análise similar à do caso 3
m
m
m
m
a ...... a b ...... b a ...... a b ...... b
z
uv x y
21
Outros casos:
m m m m
vxy está em a b a b
ou
m m m m
a b a b
ou
m m m m
a b a b
Análise similar à do caso 1:
m m m m
a b a b
22
Mai casos:
m m m m
vxy sobrepõe a b a b
ou
m m m m
a b a b
Analise similar à dos casos 2,3,4:
m m m m
a b a b
23
Não existem outros casos a considerar
Como | vxy | m, é impossível que
vxy sobreponha:
m m m m
a b a b
ou
m m m m
a b a b
ou
m m m m
a b a b
24
Em todos os casos obtivemos contradição
Portanto: A hipótese original de que
L  {ww : w {a, b}*}
é livre de contexto deve ser falsa
Conclusão:
L não é livre de contexto
25
Linguagens Não Livres de Contexto
{ww : w {a, b}}
{a b c : n  0}
n n n
{a : n  0}
n!
Linguagens Livres de Contexto
{a b : n  0}
n n
{ww : w  {a, b}*}
R
26
Teorema: A linguagem
n!
L  {a : n  0}
não é livre de contexto
Prova:
Use o Lema do Bombeamento
para linguagens livres de contexto
27
L  {a : n  0}
n!
Suponha por contradição que
L
é livre de contexto
Como L é livre de contexto e infinita
podemos aplicar o lema do bombeamento
28
L  {a : n  0}
n!
O Lema do Bombeamento nos dá
um numero mágico m tal que:
Dado um string de
L com comprimento ³ m
tomamos: a
m!
L
29
L  {a : n  0}
n!
Podemos escrever:
com
| vxy | m
a
e
m!
 uvxyz
| vy | 1
O Lema do Bombeamento diz:
uv xy z  L para todo i  0
i
i
30
L  {a : n  0}
n!
a
m!
 uvxyz
| vxy | m
| vy | 1
Examinemos todas as possíveis localizações
m
!
do string vxy em a
Existe apenas um caso a considerar
31
L  {a : n  0}
n!
a
m!
| vxy | m
 uvxyz
| vy | 1
m!
a ............... a
u v x y z
va
k1
ya
k2
1  k1  k2  m
32
L  {a : n  0}
n!
a
m!
| vxy | m
 uvxyz
| vy | 1
m!k1  k2
a ........................... a
u v2 x y 2 z
va
k1
ya
k2
1  k1  k2  m
33
L  {a : n  0}
n!
a
m!
| vxy | m
 uvxyz
m! k
a ........................... a
u v2 x y 2 z
va
k1
ya
k2
| vy | 1
k  k1  k2
1 k  m
34
L  {a : n  0}
n!
a
m!
| vxy | m
 uvxyz
a
m! k
| vy | 1
 uv xy z
2
2
1 k  m
35
Como
1  k  m, para m  2 temos:
m! k  m! m
 m! m!m
 m!(1  m)
 (m  1)!
m! m! k  (m  1)!
36
L  {a : n  0}
n!
a
m!
 uvxyz
| vxy | m
| vy | 1
m! m! k  (m  1)!
a
m! k
 uv xy z  L
2
2
37
L  {a : n  0}
n!
a
m!
 uvxyz
| vxy | m
Entretanto, do Lema do Bomb.:
a
m! k
| vy | 1
uv xy z  L
2
2
 uv xy z  L
2
2
Contradição!!!
38
Obtivemos uma contradição
Portanto:
A hipótese original de que
L  {a : n  0}
n!
é livre de contexto deve ser falsa
Conclusão:
L não é livre de contexto
39
Linguagens Não Livres de Contexto
{a b c : n  0}
n n n
n2 n
{a b : n  0}
{ww : w {a, b}}
{a : n  0}
n!
Linguagens Livres de Contexto
{a b : n  0}
n n
{ww : w  {a, b}*}
R
40
Teorema: A linguagem
n2 n
L  {a b : n  0}
não é livre de contexto
Prova:
Use o Lema do Bombeamento
para linguagens livres de contexto
41
2
L  {a b : n  0}
n
n
Suponha por contradição que
L
é livre de contexto
Como L é livre de contexto e infinita
podemos aplicar o lema do bomneamento
42
2
L  {a b : n  0}
n
n
Lema do Bomenamento nos dá
um número mágico m tal que:
Dado um string de
tomemos:
L com comprimento ³ m
a
m
2
b
m
L
43
2
L  {a b : n  0}
n
Podemos escrever:
com
a
n
m
2
b  uvxyz
m
| vxy | m e | vy | 1
O Lema do Bombeamento diz:
uv xy z  L para todo i  0
i
i
44
2
L  {a b : n  0}
n
a
m
2
n
b  uvxyz
m
| vxy | m
| vy | 1
Examinemos todas as possíveis localizações
da string
vxy em a
m
2
b
m
45
2
L  {a b : n  0}
n
a
m
2
b  uvxyz
m
Caso mais complicado:
n
| vxy | m
| vy | 1
m
v em a
m
y em b
2
m
m
a ..................... a b ...... b
u
v x y z
46
2
L  {a b : n  0}
n
a
m
2
va
| vxy | m
b  uvxyz
k1
m
yb
n
k2
| vy | 1
1  k1  k2  m
2
m
m
a ..................... a b ...... b
u
v x y z
47
2
L  {a b : n  0}
n
2
n
b  uvxyz
| vxy | m
Sub-caso mais complicado:
k1  0
a
m
va
k1
m
yb
k2
| vy | 1
e
k2  0
1  k1  k2  m
2
m
m
a ..................... a b ...... b
u
v x y z
48
2
L  {a b : n  0}
n
2
n
b  uvxyz
| vxy | m
Sub-caso mais complicado:
k1  0
a
m
va
k1
m
yb
k2
| vy | 1
e
k2  0
1  k1  k2  m
m  k1 m  k2
a ............... a b ... b
u
0 x 0z
2
v
y
49
2
L  {a b : n  0}
n
2
n
b  uvxyz
| vxy | m
Sub-caso mais complicado:
k1  0
a
m
va
m
k1
yb
a
k2
m 2  k1 m  k2
b
| vy | 1
e
k2  0
1  k1  k2  m
 uv xy z
0
0
50
k1  0
e
k2  0
1  k1  k2  m
(m  k 2 )  (m  1)
2
2
 m  2m  1
2
 m  k1
2
m  k1  (m  k2 )
2
2
51
2
L  {a b : n  0}
n
a
m
2
b  uvxyz
m
n
| vxy | m
m  k1  (m  k2 )
2
2
m  k1 m k2
a
b
| vy | 1
2
 uv xy z  L
0
0
52
2
L  {a b : n  0}
n
a
m
2
b  uvxyz
m
n
| vxy | m
uv xy z  L
0
Entretanto, do Lema do Bomb.:
2
m  k1 m k2
a
b
| vy | 1
0
 uv xy z  L
0
0
Contradição!!!
53
Quando examinamos o restante dos casos
também obtemos contradição
54
Em todos os casos obtemos contradição
Portanto: A hipótese original de que
n2 n
L  {a b : n  0}
é livre de contexto deve ser falsa
Conclusão:
L não é livre de contexto
55