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 xyzA e |y|≥k, existem cadeias u,v,w tais que y=uvw, v≠ε, e para todo i≥0, a cadeia xuyivwzA

Negando (P)Teorema. Seja A um conjunto de cadeias

e suponha que:

(~P) Para todo k≥0 existem cadeias x,y,z com xyzA e |y|≥k, e para todas cadeias u,v,w tais que y=uvw, v≠ε, e existe i≥0, tal que cadeia xuyivwzA.

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 xyzA e |y|≥k.• Daí ele pega u,v,w tais que y=uvw,

v≠ε, • Você mostra o i≥0, com xuyivwzA

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_mbakA

Minimização de Estados remover estados inalcançáveis ou colapsando

estados equivalentes.

a,b

a b a

a,b

b

a b a

b

b

aa

a

b

ba

Um autômato mínimo

b

a b a

a,ba

b

Resumindo ...

• dado M = (Q, , , s, F):– Livrar_se dos estados inalcançáveis,

i.e. dos estados q tais que não existe cadeia x* tal que *(s,x)=q.

– Colapse estados equivalentes

Mais exemplos

a,b

a

b

a,ba,b

a,b

a,ba,b

a

b

a,b

a

a,b

a,b

a

b

a,b

a,ba,b a,b

b

Ainda mais exemplos

a,b

a

b

a,b

a

a,b

a,b

a,b

a

b a,b

b

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=*(s,x)F e q=*(s,y)Fcolapsar p com q aceitar y ou

rejeitar x.• o colapso de p e q implica no

colapso de (p,a) com (q,a)

A equivalência

• Logo, p e q não podem ser colapsados se

*(p,x)F e *(q,x)F• Então definamos uma relação de

equivalência ≈ sobre Q por:p ≈ q

se, e somente se x*(*(p,x)F*(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’,, ’,s’, F’)

onde:Q’={[p] | pQ}’([p],a)=[(p,a)]s’=[s]F’={[p] | pF}

Resultados Úteis

Lema 1. Se p≈q, então (p,a)≈(q,a). Equivalentemente, se [p]=[q] então [(p,a)]=[(q,a)].

Lema2. pF sss [p]F’.

Lema3. ’*([p],x)=[*(p,x)]

Teorema. L(M/≈)=L(M)

Prova. Para x *,

x L(M/≈) sss ’*(s’,x) F’ def. de aceita

sss’*([s],x) F’ def. de s’

sss[*(s,x)] F’ lema 3

sss*(s,x) F lema 2

sssx L(M) def. de aceita

qed

M/≈ não pode ser mais colapsado

• Defina[p]~[q]

sss x*(’*([p],x)F’’*([q],x)F’)

[p]~[q]

x*(’*([p],x)F’’*([q],x)F’)

x*([*(p,x)]F’[*(q,x)]F’) lema 3 x*(*(p,x)F*(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 pF e qF ou vice_versa.

3. Repita até que não poder mais: se existe um par desmarcado {p,q} tal que {(p,a),(q,a)} é marcado para algum a, então marque {p,q}.

4. Quando acabar 3, p≈q sss {p,q} é desmarcado.

1 _ 2 _ _ 3 _ _ _ 4 _ _ _ _ 5 _ _ _ _ _ 0 1 2 3 4

■ ■ ■ ■ ■ ■ ■ ■ ■

■■

Exemplo

a,b

■ ■

0

2

a

b

a,b

a,b

b

b

3

4

1

5

a,b

a,ba,b a,b

Corretude do AlgorítmoQ={{p,q} | p,qQ}={{p,q} | p≠q} {{p} |

pQ}

logo existem ( )+n=(n2+n)/2.

seja agora Δ: Q → QΔ({p,q},a)={(p,a),(q,a)}

e F ={{p,q} | pF, qF }

X:= F repeat X’:=X; X:=X {{p,q}|a.

Δ({p,q},a)X}until X=X’

• X é o conjunto dos marcados

n2

Corretude do Algorítmo

X = {{p,q} | x*. Δ*({p,q},x}F} = {{p,q} | x*. *(p,x)F,*(q,x)F }

= {{p,q} |(x*.(*(p,x)F*(q,x)F ))}

= {{p,q} | (p≈q)