Uma variação do Lema do
Bombeamento
• Reformularemos o enunciado do
Lema de maneira a torná-lo
mais facilmente aplicado em
algumas situações.
• A reformulação permitirá o uso
de um método de prova baseado
num jogo contra o diabo
Variação do Lema
Teorema. Seja A um conjunto
regular. Então a seguinte
propriedade se dá sobre A:
(P) Existe k≥0 tal que para
quais_quer cadeias x,y,z com
xyzA e |y|≥k, existem cadeias
u,v,w tais que y=uvw, v≠ε, e para
todo i≥0, a cadeia xuyivwzA
Negando (P)
Teorema. Seja A um conjunto de
cadeias e suponha que:
(~P) Para todo k≥0 existem cadeias
x,y,z com xyzA e |y|≥k, e para
todas cadeias u,v,w tais que y=uvw,
v≠ε, e existe i≥0, tal que cadeia
xuyivwzA.
Então A não é regular.
Jogando contra o diabo
O diabo quer mostrar que A é regular
e voçê que não!
• Ele então pega k.
• Você vai escolhe xyzA e |y|≥k.
• Daí ele pega u,v,w tais que y=uvw,
v≠ε,
• Você mostra o i≥0, com xuyivwzA
Exemplo de Uso
• No exercício 5 último foi pedido para
mostrar que {x{a, b, c}* |x é
palíndrome, i.e., x=rev(x)} não é
regular.
• Dado k do diabo basta escolher x= ε,
y=ak e z=bak. Qualquer escolha u,v,w
do diabo com, digamos |v|=m>0, basta
escolher i=0 e
xuv0wz=xuwz=ak_mbakA
Minimização de Estados
remover estados inalcançáveis ou
colapsando estados equivalentes.
a
b
a
a,b
a,b
b
a
a
b
a
a
b
b
b
a
a
b
Um autômato mínimo
b
a
b
a
b
a
a,b
Resumindo ...
• dado M = (Q, , d, s, F):
– Livrar_se dos estados
inalcançáveis, i.e. dos estados q
tais que não existe cadeia x*
tal que d*(s,x)=q.
– Colapse estados equivalentes
Mais exemplos
a
a,b
a,b
a,b
a,b
a,b
b
a,b
a
a
a,b
b
a,b
a,b
b
a,b
a,b
a,b
b
a,b
a
Ainda mais exemplos
a
a
a,b
b
a,b
a,b
b
a,b
a,b
b
a,b
a
A Construção do Quociente
• Como saber com segurança que
dois estados podem ser colapsados
• como fazer o colapso formalmente?
• como determinar se mais colapsos
podem ser feitos?
• nunca colapsaremos um estado
que rejeita com um que aceita:
p=d*(s,x)F e q=d*(s,y)F
colapsar p com q aceitar y ou
rejeitar x.
• o colapso de p e q implica no
colapso de d(p,a) com d(q,a)
A equivalência
• Logo, p e q não podem ser
colapsados se
d*(p,x)F e d*(q,x)F
• Então definamos uma relação
de equivalência ≈ sobre Q por:
p≈q
se, e somente se
x*(d*(p,x)Fd*(q,x)F)
• não é difícil mostrar que de fato ≈
é uma relação de equivalência.
• [p]:={q|q≈p}
• p≈q sss [p]=[q]
O Autômato Quociente
• Dado M, definamos
M/≈ = (Q’,, d’,s’, F’)
onde:
Q’={[p] | pQ}
d’([p],a)=[d(p,a)]
s’=[s]
F’={[p] | pF}
Resultados Úteis
Lema 1. Se p≈q, então d(p,a)≈d(q,a).
Equivalentemente, se [p]=[q] então
[d(p,a)]=[d(q,a)].
Lema2. pF sss [p]F’.
Lema3. d’*([p],x)=[d*(p,x)]
Teorema. L(M/≈)=L(M)
Prova. Para x  *,
x  L(M/≈) sss d’*(s’,x)  F’ def. de aceita
sss d’*([s],x)  F’ def. de s’
sss [d*(s,x)]  F’ lema 3
sss d*(s,x)  F lema 2
sss x  L(M) def. de aceita
qed
M/≈ não pode ser mais
colapsado
• Defina
[p]~[q]
sss
x*(d’*([p],x)F’d’*([q],x)F’)
[p]~[q]
x*(d’*([p],x)F’d’*([q],x)F’)
x*([d*(p,x)]F’[d*(q,x)]F’) lema 3
x*(d*(p,x)Fd*(q,x)F’) lema 2
 p≈q
[p]=[q]
Algorítmo de Minimização
1. Escreva uma tabela dos pares {p,q},
inicialmente desmarcados
2. Marque {p,q} se pF e qF ou
vice_versa.
3. Repita até que não poder mais: se
existe um par desmarcado {p,q} tal
que {d(p,a),d(q,a)} é marcado para
algum a, então marque {p,q}.
4. Quando acabar 3, p≈q sss {p,q} é
desmarcado.
Exemplo
a
3
1
a,b
b
5
0
b
b
a,b
2
a,b
4
a,b
a,b
a,b
a,b
1
2
3
4
5
_■
_■
_■
_■
_■
0
_
■_
■_
■
_
1
■
_
■
_ _
_■ ■_ ■_
2 3 4
Corretude do Algorítmo
Q={{p,q} | p,qQ}
={{p,q} | p≠q}  {{p} | pQ}
logo existem
n
(2 )+n=(n2+n)/2.
X:= F
repeat
X’:=X;
X:=X 
{{p,q}|a. Δ({p,q},a)X}
until X=X’
seja agora Δ: Q → Q
Δ({p,q},a)={d(p,a),d(q,a)}
e F ={{p,q} | pF, qF }
• X é o conjunto dos
marcados
Corretude do Algorítmo
X = {{p,q} | x*. Δ*({p,q},x}F}
= {{p,q} | x*. d*(p,x)F,d*(q,x)F }
= {{p,q} |(x*.(d*(p,x)Fd*(q,x)F ))}
= {{p,q} |
(p≈q)