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

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


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


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


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


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


Versão miniatura

17


Divida em dois times.ACEITA vs.REJEITA

18


O rótulo 0 não causa divisão nos times

19


O rótulo 1 causa divisão do timemaior em 2

20


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


100100101

24


100100101

25


100100101

26


100100101

27


100100101

28


100100101

29


100100101

30


100100101

31


100100101

ACEITA.

32


10000

33


10000

34


10000

35


10000

36


10000

37


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


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


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


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


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


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


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


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


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


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


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


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


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)

Documents

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