Minimização de DFAs
1
Minimização de DFAs
1. Eliminação e estados inatingíveis
2. “Merge” de estados indistinguíveis
2
Estados Inatingíveis - exemplo
a
a
b
b
a
b
estado inatingível
3
Estados Inatingíveis -algoritmo
reachable_states := {q0}
new_states := {q0}
while (new_states ≠ the empty set) do
temp := Æ
for each q in new_states do
for each c in Σ do
temp := temp ∪ {p | p=δ(q,c)}
new_states := temp - reachable_states
reachable_states := reachable_states ∪ new_states
unreachable_states := Q - reachable_states
4
Equivalência entre estados
• O conjunto de estados de um DFA pode ser
particionado em classes de equivalência, de
acordo com o seu “comportamento”
• Dois estados q1 e q2 pertencem à mesma classe
de equivalência -- são equivalentes -- se, para
qualquer palavra w, todos os caminhos com rótulo
w a partir de q1 e a partir de q2 levam, em ambos
os casos, a um estado final, ou, levam, em ambos
os casos, a um estado não final.
5
Classes de Equivalência – Hopcroft (1971)
A partição inicial tem 2 subconjuntos claramente distintos:
estados de aceitação e estados de rejeição.
O algoritmo repetidamente escolhe um conjunto A da
partição corrente e um símbolo c do alfabeto, e divide
cada um dos conjuntos da partição em dois subconjuntos
(possivelmente vazios): aqueles estados que levam a A, em
uma transição sobre c, e aqueles que não levam a A.
Como já se determinou previamente que A tem
comportamento distinto dos demais conjuntos da partição,
subconjuntos que levam a A também têm comportamento
diferente daqueles que não levam a A
O algoritmo termina quando não se pode mais dividir nenhum
conjunto da partição.
6
Estados Indistingíveis - exemplo
Começa com uma partição
em 2 classes 05 e 12346.
Refinamento 1:
12346 → 1234 e 6
devido a a
Refinamento 2:
05 → 0 e 5
devido a a
Refinamento 3:
1234 → 1 e 24 e 3
devido a b
2 e 4 são indistinguíveis
7
Notação
Seja Q o conjunto de estados de um DFA e a
um símbolo do alfabeto.
Sejam B,C ⊆ Q conjuntos de estados.
(B · a) = {q’ | δ(q,a)=q’, q ∈B}
o pair (C,a) splits o conjunto B se
(B · a)∩C ≠
eÆ(B · a)∩(Q-C) ≠
Æ
8
Classes de Equivalência – Hopcroft (1971)
P := {F,Fc}
-- inicializa partição corrente P
for each a∈A do
add((min(F,Fc),a),W)
-- inicializa conjunto W
while W ≠ Æ do
(C,a) := some(W)
-- escolhe um elemento de W
for each B ∈ P split by (C,a) do
B′,B′′ := split(B,C,a)
substitua B por B′ e B′′ em P
for each b ∈ A do
if (B,b) ∈ W then
substitua (B, b) por (B′, b) e (B′′, b) em W
else
add((min(B′, B′′), b), W)
9
Exemplo – de novo
Inicializa partição P: 05|12346
Conjunto W : (05, a), (05, b)
Par escolhido (C,a): (05, a)
Conjunto B: 12346
Estados que levam a 05: 6
Classe a separar: 12346 → 1234|6
Pares a adicionar: (6, a) e (6, b)
Classe a separar : 05 → 0|5
Par a adicionar: (5, a) (ou (0, a))
Par a substituir: (05,b) por (0,b) e (5,b)
Nova partição P: 0|1234|5|6
Novo conjunto W:
(0, b), (6, a), (6, b), (5, a), (5, b)
10
Classes de Equivalência – Hopcroft (1971)
• Tempo de execução do algoritmo, no pior
caso, é O(n s log n), onde n é o número de
estados e s é o número de símbolos do
alfabeto. Ou seja, é O(n log n) para DFAs
sobre um alfabeto fixo.
• Não funciona para NFAs (só para DFAs)
11
Minimização de DFAs
Alguns outros algoritmos de minimização:
• Algoritmo de Moore (1956): também por
refinamento de partições O(n2s)
• Algoritmo de Brzozowski (1963): aplica-se
também para NFA M O(2n)
•
•
•
•
•
•
‘’Inverter’’ M, para obter um NFA N para LR
Eliminar os estados inatingíveis de N
Converter N para o DFA equivalente M’
Inverter M’, obtendo um novo NFA N’’ para L
Converter N’ para o DFA equivalente M’’
M’’ é o DFA mínimo para L
12