Mais Aplicações
do
Lema do Bombeamento
1
Lema do Bombeamento:
• Dada uma linguagem regular infinita
• existe um inteiro
m
w L com | w |  m
• para todo string
• podemos escrever
• com
L
w x y z
| x y |  m e | y | 1
• tal que:
xy z  L
i
i  0, 1, 2, ...
2
Linguagens não regulares
L  {ww : w  *}
R
Linguagens Regulares
3
Teorema: A linguagem
L  {ww : w  *}
R
  {a, b}
não é regular
Prova:
Usando o Lema do Bombeamento
4
L  {ww : w  *}
R
Suponha por contradição
que L é uma linguagem regular
Como L é infinita
podemos usar o Lema do Bombeamento
5
L  {ww : w  *}
R
Seja
m o inteiro do Lema do Bombeamento
Tome um string
w tal que: w  L
e comprimento
tome w  a
| w| m
m m m m
b b a
6
Escreva
a b b a xyz
m m m m
Do Lema do Bombeamento
devemos ter que | x y |  m,
m
| y | 1
m m m
a b b a  a...aa...a...ab...bb...ba...a
m m m m
x
y  a , k 1
y
z
k
7
Temos:
x y za b b a
m m m m
y  a , k 1
k
Do Lema do Bombeamento:
xy z  L
i
i  0, 1, 2, ...
Então:
xy z  L
2
x y zx y y za
2
m k m m m
b b a
 L
8
Portanto:
MAS:
a
m k m m m
b b a
L
L  {ww : w  *}
R
a
m k m m m
b b a
L
CONTRADIÇÃO!!!
9
Portanto:
Conclusão:
Nossa hipótese de que L
é uma linguagem regular
não é verdadeira
L não é uma linguagem regular
10
Linguagens não regulares
n l n l
L  {a b c
: n, l  0}
Linguagens Regulares
11
Torema: A linguagem
n l n l
L  {a b c
: n, l  0}
não é regular
Prova:
Usando o Lema do Bombeamento
12
n l n l
L  {a b c
: n, l  0}
Suponha por contradição
que L seja uma linguagem regular
Como L é infinita
podemos usar o Lema do Bombeamento
13
n l n l
L  {a b c
Seja
: n, l  0}
m o inteiro do Lema do Bombeamento
Tome um string
w tal que: w  L
e comprimento
tome
| w| m
wa b c
m m 2m
14
m m 2m
Escreva
a b c
xyz
Pelo Lema do Bombeamento
devemos ter que | x y |  m,
m
m m 2m
a b c
| y | 1
m
2m
 a...aa...aa...ab...bc...cc...c
x
y  a , k 1
y
z
k
15
x y za b c
m m 2m
Temos:
y  a , k 1
k
Do Lema do Bombeamento:
xy z  L
i
i  0, 1, 2, ...
Então:
xy z  L
0
x y zxza
0
mk m 2m
b c
 L
16
Portanto:
MAS:
a
mk m 2m
b c
n l n l
L  {a b c
a
mk m 2m
b c
L
: n, l  0}
L
CONTRADIÇÃO!!!
17
Portanto:
Nossa hipótese de que L
é uma linguagem regular
não é verdadeira
Conclusão: L não é uma linguagem regular
18
Linguagens não regulares
L  {a : n  0}
n!
Regular languages
19
Teorema: A linguagem
L  {a : n  0}
n!
não é regular
n!  1 2  (n  1)  n
Prova:
Usando o Lema do Bombeamento
20
L  {a : n  0}
n!
Suponha por contradição
que L é uma linguagem regular
Como L é infinita
podemos usar o Lema do Bombeamento
21
L  {a : n  0}
n!
Seja
m o inteiro do Lema do Bombeamento
Tome um string
w tal que: w  L
e comprimento
tome
wa
| w| m
m!
22
Escreva
a
m!
xyz
Pelo Lema do Bombeamento
devemos ter que | x y |  m,
m
a
m!
| y | 1
m!m
 a...aa...aa...aa...aa...a
x
y
y  a , 1 k  m
z
k
23
Temos:
x y za
m!
y  a , 1 k  m
k
Do Lema do Bombeamento:
xy z  L
i
i  0, 1, 2, ...
Então:
xy z  L
2
x y zx y y za
2
m! k
 L
24
Portanto:
a
E como:
Existe um
m! k
L
1 k  m
L  {a : n  0}
n!
p:
m! k  p!
1 k  m
25
Entretanto:
m! k  m! m
 m! m!
para
m 1
 m!m  m!
 m!(m  1)
 (m  1)!
m! k  (m  1)!
m! k  p! para qualquer p
26
Portanto:
a
m! k
L
MAS: L  {a : n  0} e 1  k  m
n!
a
m! k
L
CONTRADIÇÃO!!!
27
Portanto:
Nossa hipótese de que L
é uma linguagem regular
não é verdadeira
Conclusion: L não é uma linguagem regular
28
Lex
29
Lex: um analisador léxico
• Um programa Lex reconhece strings
• Para cada tipo de string encontrado
o programa lex toma uma ação
30
Saída
Entrada
Var = 12 + 9;
if (test > 20)
temp = 0;
else
while (a < 20)
temp++;
programa
Lex
Identifier: Var
Operandor: =
Integer: 12
Operandor: +
Integer: 9
Semicolumn: ;
Keyword: if
Parenthesis: (
Identifier: test
....
31
Em Lex strings são descritos
por expressões regulares
programa Lex
Expressões regulares
“+”
“-”
“=“
/* operadores */
“if”
“then”
/* keywords */
32
programa Lex
Expressões regulares
(0|1|2|3|4|5|6|7|8|9)+
(a|b|..|z|A|B|...|Z)+
/* integers */
/* identifiers */
33
inteiros
(0|1|2|3|4|5|6|7|8|9)+
[0-9]+
34
identificadores
(a|b|..|z|A|B|...|Z)+
[a-zA-Z]+
35
Cada expressão regular
tem uma ação associada
Exemplos:
Expressão Regular
Ação
\n
linenum++;
[0-9]+
prinf(“integer”);
[a-zA-Z]+
printf(“identifier”);
36
Estrutura Interna do Lex
Lex
Expressões
Regulares
NFA
DFA
Os estados finais do DFA
são associados com ações
string
DFA
Mínimo
Simulador
de DFA
[tokens]
42