1
Minimização; Lema do Bombeamento.
Agenda
Hoje Minimização de DFAs Lema do Bombeamento para
Linguagens Regulares
Para as próximas aulas: Leia Caps. 1.4 (Sipser)
3
Estados Equivalentes.Exemplo
Considere os estados de aceitação c e g. Eles são ambos estados que, uma vez atingidos, nunca se sai deles, desde que se leia 0 ou 1.
Q: Precisamos desses dois estados?
a
b
1
d
0,1e
0,1
1
c
0,1
gf
0
0
0
01
1
4
Estados Equivalentes.Exemplo
R: Não, eles podem ser unificados como se mostra abaixo.
Q: Existem outros estados que podem ser unificados, porque quaisquer sufixos subsequentes produzem o mesmo resultado?
a
b
1
d 0,1
e1
0,1
cg
f
0
0 0
01
1
5
Estados Equivalentes.Exemplo
R: Sim, b e f. Note que se estamos em b ou f então:
1. se o string termina, é rejeitado em ambos os casos2. se proxchar=0, aceita c/ qq sufixo em ambos os casos3. Se proxchar=1, rejeita c/ qq sufixo em ambos os
casos
Portanto, unifique b com f.
a
b
1
d 0,1
e1
0,1
cg
f
0
0 0
01
1
6
Estados Equivalentes.Exemplo
Intuitivamente, dois estados são equivalentes se todos as computações subsequentes a partir deles são iguais.
Q: Dê uma caracterização formal de equivalência entre estados.
a
0,1
d 0,1
e1
0,1
cg
bf
0
01
7
Estados Equivalentes.Exemplo
DEF: Dois estados q e q ’ em um DFA M = (Q, , , q0, F ) são equivalentes (ou indistinguiveis) se, para quaisquer strings u *, os estados a que u leva, quando lido a partir de q ou de q ’ são ambos de aceitação, ou ambos não são de aceitação.
Estados equivalentes podem ser unificados em um único, sem que isso afete o comportamento de M.
8
Concluindo o ExemploQ: Existem outras maneiras de
simplificar o autômato abaixo?
a
0,1
d 0,1
e1
0,1
cg
bf
0
01
9
Estados InúteisR: Sim: elimine o estado d.A eliminação de estados inúteis
(inatingíveis a partir do estado inicial) não altera a linguagem aceita.
a
0,1
0,1
e
0,1
cg
bf0
1
10
Algoritmo de Minimização.DEF: Um autômato é irredutível se
Não contém estados inúteis, e não contém estados distintos equivalentes.
O objetivo do algoritmo de minimização é criar um autômato irredutível a partir de um autômato dado. Pode-se mostrar que esse algoritmo de fato produz o menor DFA possível equivalente ao DFA original. Portanto o nome “minimização”.
O algoritmo de minimização trabalha ao inverso do que vimos no exemplo anterior. Começa pelo menor número possível de estados e cria novos estados quando é forçado a isso. Vamos explicar com um jogo:
11
O Jogo MINIMIZAR0. Todos os jogadores inúteis são eliminados.1. O jogo prossegue em rodadas. 2. Começa com 2 times: ACEITA vs. REJEITA.3. Cada rodada consiste de sub-rodadas, uma para
cada time.4. Dois membros de um time concordam se, para um
dado rótulo, passam o bastão para o mesmo time. Caso contrário, discordam.
5. Durante uma sub-rodada, membros que discordam são divididos em novos times maximais de membros concordantes entre si.
6. O jogo TERMINA quando se passa uma rodada sem que nenhum time seja dividido.
12
O Jogo MINIMIZAR
a
b
1
d
0,1e
0,1
1
c
0,1
gf
0
0
0
01
1
13
Algoritmo de Minimização.(Refinamento da Partição)
DFA minimize(DFA (Q, , , q0, F ) )
remova qq estado q não atingível a partir de q0 Partition P = {F, Q - F } boolean Consistent = false while (not Consistent ) Consistent = true for(every Set S,T P e char a ) Set temp = {q T | (q,a) S } if (temp != Ø && temp != T ) // S ,T não concordam
Consistent = false P = (P T ){temp, Ttemp} // divide T
return defineMinimizor( (Q, , , q0, F ), P )
14
Algoritmo de Minimização.(Refinamento da Partição)
DFA defineMinimizor(DFA (Q, , , q0, F ), Partition P )
Set Q ’ = P // cada partição é um estado do autômato resultante
// o estado inicial q ’0 é a partição que contém q0
State q ’0 = the set in P which contains q0
// F’ consiste das partições que contém apenas estados finais
F ’ = { S P | S F } computa a nova função de transição ’
for (each S P, a define ’ (S,a) = the set T P which contains
the states ’(S,a) return (Q ’, , ’, q ’0, F ’ )
15
Minimização: Exemplo
Considere o DFA
16
Minimização: Exemplo
Versão miniatura
17
Minimização: Exemplo
Divida em dois times.ACEITA vs.REJEITA
18
Minimização: Exemplo
O rótulo 0 não causa divisão nos times
19
Minimização: Exemplo
O rótulo 1 causa divisão do timemaior em 2
20
Minimização: Exemplo
Nenhuma divisão mais. TERMINOU!
21
Minimização: Exemplo.Resultado
Os estados do autômato mínimo são os times resultantes. As transições entre esses estados são consolidadas. O estado inicial é o time que contémo estado inicial original.
22
Minimização: Exemplo.Compare
100100101
23
Minimização: Exemplo.Compare
100100101
24
Minimização: Exemplo.Compare
100100101
25
Minimização: Exemplo.Compare
100100101
26
Minimização: Exemplo.Compare
100100101
27
Minimização: Exemplo.Compare
100100101
28
Minimização: Exemplo.Compare
100100101
29
Minimização: Exemplo.Compare
100100101
30
Minimização: Exemplo.Compare
100100101
31
Minimização: Exemplo.Compare
100100101
ACEITA.
32
Minimização: Exemplo.Compare
10000
33
Minimização: Exemplo.Compare
10000
34
Minimização: Exemplo.Compare
10000
35
Minimização: Exemplo.Compare
10000
36
Minimização: Exemplo.Compare
10000
37
Minimização: Exemplo.Compare
10000
REJEITA.
38
Minimização: Prova
O algoritmo apresentado produz um FA irredutível. Porque esse FA seria o menor FA possível que reconhece a linguagem aceita pelo FA original?
Questão análoga em cálculo: Por que um mínimo local seria um mínimo global? Nem sempre é o caso!
39
Minimização: Prova
THM (Myhill-Nerode): O algoritmo de minimização produz um autômato mínimo equivalente.
Prova. Mostraremos que qq autômato irredutível é mínimo para a linguagem L que ele aceita:
Dizemos que strings u,v * são indistinguíveis se para todo sufixo x, ux L sse vx L .
Note que se u ev são distinguíveis, os caminhos, a partir do estado inicial, rotulados por u e por v devem terminar em estados diferentes.
40
Minimização: Prova
Consequentemente, o número de estados em um DFA para L deve ser pelo menos igual ao ao número de strings mutuamente distinguíveis de L.
Mas um DFA irredutível tem a propriedade de que todo estado dá origem a outro string mutuamente distinguível do anterior!
Portanto, qq outro DFA para L deve ter pelo menos tantos estados quantos os de um DFA irredutível.
Vejamos como essa prova funciona:
41
Minimização: Prova. Exemplo
A “spanning tree” dos strings {,0,01,00} é um conjunto de estados mutuamente distinguíveis (caso contrário ocorreria redundância, DFA teria sido reduzido).
Qualquer outro DFA para L tem 4 estados.
a
0,1
0,1
e
0,1
cg
bf0
1
42
Lema do BombeamentoMotivação
Considere a linguagem L1 = 01* = {0, 01, 011, 0111, … }
O string 011 é dito bombeável em L1 porque podemos tomar a porção sublinhada e bombeá-la (repeti-la) tantas vezes quanto se queira, obtendo sempre strings em L1.
Q: Quais dos seguintes strings são bombeáveis?01111010
43
Lema do BombeamentoMotivação
0 0
1
0
1. Bombeável: 01111, 01111, 01111, 01111, etc.
2. Bombeável: 01
3. 0 não bombeável
Seja L2 a linguagem definida pelo autômato:
Q: 01010 é bombeável?
44
Lema do BombeamentoMotivação
0 0
1
0
A: Bombeável: 01010, 01010. Os substrings sublinhados correspondem a ciclos no FA!
Ciclos do FA podem ser repetidos um no. de arbitrário de vezes: bombeamento.
Seja L3 = {011,11010,000,
Q: Que strings são bombeáveis?
45
Lema do BombeamentoMotivação
A:Nenhum! Quando um string pode ser bombeado (de modo não trivial), é sempre possível obter infinitos possíveis strings por meio desse bombeamento. Portanto, linguagens finitas não satisfazem a propriedade de bombeamento.
O Lema do Bombeamento provê um critério para quando strings podem ser bombeados:
46
Lema do Bombeamento
THM: Dada uma linguagem regular L, existe um número p (número de bombeamento) tal que qualquer string em L de comprimento p é bombeável nos seus p primeiros simbolos. Em outras palavras, para todo u L, tal que |u | p, podemos escrever: u = xyz (x é um prefixo, z é umsufixo) |y | 1 (a parte do meio y é não vazia) |xy| p (bomb. nos p primeiros simbolos) xyiz L for all i 0 (a partey pode ser bombeada)
47
Lema do Bombeamento: Prova
EX: Mostre que pal={x*|x =x R} não é regular.1. Suponha pal regular2. Então ela tem um no. de bombeamento p3. Mas… considere o string 0p10p. Esse string
pode ser bombeado nos p primeiros símbolos? A resposta é NÃO, porque qualquer aumento da primeira porção - 0p- resulta em um string que não é um palindromo.
4. (2)(3) <contradição!> Portanto, nossa suposição (1) está errada e podemos concluir que pal não é uma linguagem regular
48
Lema do Bombeamento: Modelo
De modo geral, para provar que L não é regular:Suponha L regularEntão L tem um no. de bombeamento pEncontre um padrão de string envolvendo p, que pertença a L, e que não possa ser bombeado. Essa é a parte difícil.(2)(3) <contradição!> Portanto, a nossa suposição em (1) está errada e podemos concuir que L não é regular.
49
Lema do Bombeamento: Exemplo
Como as partes 1, 2 e 4 são idênticas para qualquer prova usando o lema do bombeamento, os exemplos a seguir mostram apenas a parte 3 da prova.
50
Lema do Bombeamento: Exemplo
EX: Mostre que L={a nb n| n = 0,1,2, … } não é regular.
Parte 3) Considere a pb p. Por hipótese, a parte a ser bombeada deve estar contida nos p primeiros símbolos do string. Nesse caso, obteríamos um string com mais a’s do que b’s, que não corresponde ao padrão de strings de L.
51
Lema do Bombeamento: Exemplo
Algumas vezes pode ser útil bombear para menos e não para mais, ou seja, simplesmente remover a parte y do padrão do string. Isso corresponde a tomar i = 0 no lema do bombeamento:
EX: Mostre que {a mb n| m > n} não é regular.Part 3) Considere a p+1b p. Por hipótese, podemos
bombear p/ menos um substring das p primeiras letras desse string. Como y é não vazio, isso resulta em um decréscimo do número de a’s no padrão, significando que o no. de a’s é menor ou igual ao no. de b’s. Portanto, o string resultante não pertence à linguagem!
52
Lema do Bombeamento: Exemplo
Algumas vezes precisamos examinar o resultado do bombeamento com mais cuidado:
EX: Mostre que {1n| n é primo} não é regular.Part 3) Dado p, escolhemos um número primo n
maior que p. Considere 1n. Por hipótese, podemos bombear um substring dos p primeiros simbolos de 1n. Seja m o comprimento da parte bombeada. Bombeando i vezes, obtemos o string 1(n-m)+im =1n+(i-1)m.
Q: Determine i de modo que o expoente não seja um número primo.
53
Lema do Bombeamento: Exemplo
A: Tome i = n + 1. Então o string resultante do bombeamento é
1n+(i-1)m =1n+(n+1-1)m =1n+nm=1n(1+m)
Portanto, o expoente não é um número primo (porque é divisível por n e por 1+m), significando que o string não pertence à linguagem.
54
Lema do Bombeamento: Prova
Considere um grafo com n vértices. Suponha que você anda pelo grafo, visitando um certo número de vértices.
Q: Quantos vértices você pode visitar, antes de ser forçado a visitar um mesmo vértice uma segunda vez?
55
Lema do Bombeamento: Prova
A: Se voce visita n+1 vértices, necessariamente terá que visitar um deles mais de uma vez.
Q: Porque?
56
Lema do Bombeamento: Princípio da Casa dos
Pombos
R: Princípio da Casa dos Pombos.Mais precisamente. Sua visita a n+1
vértices define a seguinte função:f : {1, 2, 3, … , n+1} {conj. card. n }
f (i ) = i-ésimo vértice visitadoComo o domínio é maior que o
codomínio, a função não pode ser injetora.
57
Lema do Bombeamento: Prova
Considere agora o string aceito u. Como L é regular por hipótese, seja M o FA que aceita L. Seja p = |Q | = no. de estados de M. Suponha |u| p. O caminho rotulado por u visita p+1 estados nos primeiros p símbolos. Então u deve visitar algum estado mais de uma vez. O sub-caminho de u conectando a primeira e a segunda visita a esse vértice é um loop, e nos dá a parte y que pode ser bombeada (contida nos p primeiros símbolos)