55
1 Mais Aplicações do Lema do Bombeamento

1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

Embed Size (px)

Citation preview

Page 1: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

1

Mais Aplicaçõesdo

Lema do Bombeamento

Page 2: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

2

Lema do Bombeamento:

existe um inteiro tal quem

para todo string mwLw || ,

podemos escrever

Para toda ling. livre de contexto infinita L

uvxyzw

com 1||and || vymvxy

e devemos ter:

0 allfor , iLzxyuv ii

Page 3: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

3

Linguagens Livres de Contexto

}0:{ nba nn

Linguagens Não Livres de Contexto

}0:{ ncba nnn

}*},{:{ bawwwR

}},{:{ bawww

Page 4: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

4

Teorema: A linguagem

}*},{:{ bawwwL

não é livre de contexto

Prova:Use o Lema do Bombeamentopara linguagens livres de contexto

Page 5: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

5

Suponha por contradição que

é livre de contexto

Como é livre de contexto e infinitapodemos aplicar o lema do bombeamento

L

L

}*},{:{ bawwwL

Page 6: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

6

O Lema do Bombeamento nos dá um número magico tal que: m

Dado um string de com comprimento

tomamos: Lbaba mmmm

}*},{:{ bawwwL

L

Page 7: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

7

Podemos escrever:

com emvxy || 1|| vy

}*},{:{ bawwwL

uvxyzbaba mmmm

O Lema do Bombeamento diz:

Lzxyuv ii para todo 0i

Page 8: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

8

Examinemos todas as possíveios localizaçõesdo string em vxy

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

mmmm baba

Page 9: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

9

Caso 1: vxyestá nos primeirosma

bbaabbaa ........................v

m m m

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x y

m

1kav 2kay 121 kk

Page 10: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

10

bbaabbaa ..................................2v

21 kkm m m

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x 2y

m

Caso 1: vxyestá nos primeirosma

1kav 2kay 121 kk

Page 11: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

11

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

Caso 1: vxyestá nos primeirosma

121 kk

Lzxyuvbaba mmmkkm 2221

Page 12: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

12

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

Case 1: vxyestá nos primeirosma

Lzxyuv 22

Contradição!!!

Lzxyuvbaba mmmkkm 2221

Estretando, do Lema do Bomb.:

Page 13: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

13

está nos primeiros

está nos primeirosCaso 2:

bbaabbaa ........................v

m m m

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x y

m

mamb

vy

1kav 2kby 121 kk

Page 14: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

14

Caso 2:

bbaabbaa ....................................2v

1km 2km m

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x 2y

m

1kav 2kby 121 kk

está nos primeiros

está nos primeirosmamb

vy

Page 15: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

15

Caso 2:

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

121 kk

Lzxyuvbaba mmkmkm 2221

está nos primeiros

está nos primeirosmamb

vy

Page 16: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

16

is in the first

is in the firstCase 2:

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

mamb

vy

Lzxyuvbaba mmkmkm 2221

Lzxyuv 22

Contradiction!!!

However, from Pumping Lemma:

Page 17: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

17

está nos primeiros

sobrepõe os primeirosCaso 3:

bbaabbaa ........................v

m m m

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x y

m

mmbamb

vy

21 kk bav 3kby 1, 21 kk

Page 18: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

18

Caso 3:

bbaabbaabbaa .................................2v

m 2k 3km

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x 2y

m

21 kk bav 3kby 1, 21 kk

1k m

está nos primeiros

sobrepõe os primeirosmmba

mbvy

Page 19: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

19

Caso 3:

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

Lzxyuvbababa mmkmkkm 22312

1, 21 kk

está nos primeiros

sobrepõe os primeirosmmba

mbvy

Page 20: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

20

Caso 3:

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

Lzxyuvbababa mmkkkm 22312

Lzxyuv 22

Contradição!!!

Entretanto, do Lema do Bomb.:

está nos primeiros

sobrepõe os primeirosmmba

mbvy

Page 21: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

21

sobrepõe os primeiros

está nos primeirosCase 4:

bbaabbaa ........................v

m m m

u z

mvxy || 1|| vyuvxyzbaba mmmm

}*},{:{ bawwwL

x y

m

mammba

vy

Análise similar à do caso 3

Page 22: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

22

Outros casos: vxy está emmmmm baba

ou

ou

mmmm baba

mmmm baba

Análise similar à do caso 1:

mmmm baba

Page 23: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

23

Mai casos: vxy sobrepõemmmm baba

ou

mmmm baba

Analise similar à dos casos 2,3,4:

mmmm baba

Page 24: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

24

Como , é impossível que sobreponha:

Não existem outros casos a considerar

mvxy ||vxy mmmm baba

ou

ou

mmmm baba

mmmm baba

Page 25: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

25

Em todos os casos obtivemos contradição

Portanto:A hipótese original de que

é livre de contexto deve ser falsa

Conclusão: não é livre de contextoL

}*},{:{ bawwwL

Page 26: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

26

Linguagens Livres de Contexto

}0:{ nba nn

Linguagens Não Livres de Contexto

}0:{ ncba nnn

}*},{:{ bawwwR

}},{:{ bawww

}0:{ ! nan

Page 27: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

27

Teorema: A linguagem

não é livre de contexto

Prova:Use o Lema do Bombeamentopara linguagens livres de contexto

}0:{ ! naL n

Page 28: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

28

Suponha por contradição que

é livre de contexto

Como é livre de contexto e infinitapodemos aplicar o lema do bombeamento

L

L

}0:{ ! naL n

Page 29: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

29

O Lema do Bombeamento nos dá um numero magico tal que: m

Dado um string de com comprimento

tomamos: Lam !

L

}0:{ ! naL n

Page 30: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

30

Podemos escrever:

com emvxy || 1|| vy

uvxyzam !

O Lema do Bombeamento diz:

Lzxyuv ii para todo 0i

}0:{ ! naL n

Page 31: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

31

Examinemos todas as possíveis localizaçõesdo string em vxy

mvxy || 1|| vy

!ma

uvxyzam !

Existe apenas um caso a considerar

}0:{ ! naL n

Page 32: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

32

v

!m

u zx y

1kav 2kay mkk 211

aa ...............

mvxy || 1|| vyuvxyzam !

}0:{ ! naL n

Page 33: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

33

2v

21! kkm

u zx 2y

1kav 2kay

aa ...........................

mvxy || 1|| vyuvxyzam !

}0:{ ! naL n

mkk 211

Page 34: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

34

2v

km !

u zx 2y

1kav 2kay

aa ...........................

mvxy || 1|| vyuvxyzam !

}0:{ ! naL n

mk 1

21 kkk

Page 35: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

35

mvxy || 1|| vyuvxyzam !

}0:{ ! naL n

mk 1

zxyuva km 22!

Page 36: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

36

)!1(

)1(!

!!

!!

m

mm

mmm

mmkm

mk 1Como , para temos:2m

)!1(!! mkmm

Page 37: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

37

mvxy || 1|| vyuvxyzam !

}0:{ ! naL n

Lzxyuva km 22!

)!1(!! mkmm

Page 38: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

38

mvxy || 1|| vyuvxyzam !

}0:{ ! naL n

Lzxyuva km 22!

Lzxyuv 22

Contradição!!!

Entretanto, do Lema do Bomb.:

Page 39: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

39

Obtivemos uma contradição

Portanto:A hipótese original de que

é livre de contexto deve ser falsa

Conclusão: não é livre de contextoL

}0:{ ! naL n

Page 40: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

40

Linguagens Livres de Contexto

}0:{ nba nn

Linguagens Não Livres de Contexto

}0:{ ncba nnn

}*},{:{ bawwwR

}},{:{ bawww

}0:{ ! nan}0:{2

nba nn

Page 41: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

41

Teorema: A linguagem

não é livre de contexto

Prova:Use o Lema do Bombeamentopara linguagens livres de contexto

}0:{2

nbaL nn

Page 42: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

42

Suponha por contradição que

é livre de contexto

Como é livre de contexto e infinitapodemos aplicar o lema do bomneamento

L

L

}0:{2

nbaL nn

Page 43: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

43

Lema do Bomenamento nos dá um número mágico tal que: m

Dado um string de com comprimento

tomemos: Lba mm 2

L

}0:{2

nbaL nn

Page 44: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

44

Podemos escrever:

com emvxy || 1|| vy

uvxyzba mm 2

O Lema do Bombeamento diz:

Lzxyuv ii para todo 0i

}0:{2

nbaL nn

Page 45: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

45

Examinemos todas as possíveis localizações

da string em vxy

mvxy || 1|| vyuvxyzba mm 2

mm ba2

}0:{2

nbaL nn

Page 46: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

46

Caso mais complicado:

bbaa ...........................v

2m m

u zx y

em

emmamb

vy

mvxy || 1|| vyuvxyzba mm 2

}0:{2

nbaL nn

Page 47: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

47

bbaa ...........................v

2m m

u zx y

1kav 2kby

mvxy || 1|| vyuvxyzba mm 2

}0:{2

nbaL nn

mkk 211

Page 48: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

48

bbaa ...........................v

2m m

u zx y

1kav 2kby

Sub-caso mais complicado: 01 k 02 k

mvxy || 1|| vyuvxyzba mm 2

}0:{2

nbaL nn

mkk 211

e

Page 49: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

49

0v

12 km 2km

u zx 0y

bbaa ..................

}0:{2

nbaL nn

mvxy || 1|| vyuvxyzba mm 2

1kav 2kby

Sub-caso mais complicado: 01 k 02 k

mkk 211

e

Page 50: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

50

}0:{2

nbaL nn

mvxy || 1|| vyuvxyzba mm 2

1kav 2kby

Sub-caso mais complicado: 01 k 02 k

mkk 211

e

zxyuvba kmkm 00212

Page 51: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

51

12

2

222

12

)1()(

km

mm

mkm

01 k 02 k mkk 211 e

221

2 )( kmkm

Page 52: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

52

}0:{2

nbaL nn

mvxy || 1|| vyuvxyzba mm 2

221

2 )( kmkm

Lzxyuvba kmkm 00212

Page 53: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

53

}0:{2

nbaL nn

mvxy || 1|| vyuvxyzba mm 2

Lzxyuvba kmkm 00212

Entretanto, do Lema do Bomb.: Lzxyuv 00

Contradição!!!

Page 54: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

54

Quando examinamos o restante dos casostambém obtemos contradição

Page 55: 1 Mais Aplicações do Lema do Bombeamento. 2 Lema do Bombeamento: existe um inteiro tal que para todo string podemos escrever Para toda ling. livre de

55

Em todos os casos obtemos contradição

Portanto:A hipótese original de que

é livre de contexto deve ser falsa

Conclusão: não é livre de contextoL

}0:{2

nbaL nn