Minimalizacja DFA
Minimalizacja DFA za pomocą twierdzenia Myphill-Nerode
Algorytm
Input - DFA
Output - Zminimalizowany DFA
Step 1- Narysuj tabelę dla wszystkich par stanów (Q i , Q j ) niekoniecznie połączonych bezpośrednio [Wszystkie są początkowo odznaczone]
Step 2- Rozważ każdą parę stanów (Q i , Q j ) w DFA, gdzie Q i ∈ F i Q j ∉ F lub odwrotnie i zaznacz je. [Tutaj F jest zbiorem stanów końcowych]
Step 3 - Powtarzaj ten krok, dopóki nie będziemy mogli już zaznaczyć stanów -
Jeśli istnieje para nieoznaczona (Q i , Q j ), zaznacz ją, jeśli para {δ (Q i , A), δ (Q i , A)} jest zaznaczona dla jakiegoś alfabetu wejściowego.
Step 4- Połącz wszystkie nieoznakowane pary (Q i , Q j ) i uczyń je jednym stanem w zredukowanym DFA.
Przykład
Użyjmy algorytmu 2, aby zminimalizować DFA pokazane poniżej.
Step 1 - Rysujemy tabelę dla wszystkich par stanów.
za | b | do | re | mi | fa | |
za | ||||||
b | ||||||
do | ||||||
re | ||||||
mi | ||||||
fa |
Step 2 - Zaznaczamy pary stanów.
za | b | do | re | mi | fa | |
za | ||||||
b | ||||||
do | ✔ | ✔ | ||||
re | ✔ | ✔ | ||||
mi | ✔ | ✔ | ||||
fa | ✔ | ✔ | ✔ |
Step 3- Postaramy się zaznaczyć przejściowo pary stanów zielonym haczykiem. Jeśli wprowadzimy 1 do stanu „a” i „f”, przejdzie to odpowiednio do stanu „c” i „f”. (c, f) jest już zaznaczone, stąd oznaczymy parę (a, f). Teraz wprowadzamy 1, aby określić „b” i „f”; przejdzie odpowiednio do stanu „d” i „f”. (d, f) jest już zaznaczone, stąd oznaczymy parę (b, f).
za | b | do | re | mi | fa | |
za | ||||||
b | ||||||
do | ✔ | ✔ | ||||
re | ✔ | ✔ | ||||
mi | ✔ | ✔ | ||||
fa | ✔ | ✔ | ✔ | ✔ | ✔ |
Po kroku 3 mamy kombinacje stanów {a, b} {c, d} {c, e} {d, e}, które są nieoznaczone.
Możemy rekombinować {c, d} {c, e} {d, e} w {c, d, e}
Stąd mamy dwa połączone stany jako - {a, b} i {c, d, e}
Więc ostateczny zminimalizowany DFA będzie zawierał trzy stany {f}, {a, b} i {c, d, e}
Minimalizacja DFA za pomocą twierdzenia o równoważności
Jeśli X i Y są dwoma stanami w DFA, możemy połączyć te dwa stany w {X, Y}, jeśli nie są rozróżnialne. Można rozróżnić dwa stany, jeśli istnieje co najmniej jeden ciąg S, taki że jeden z δ (X, S) i δ (Y, S) akceptuje, a inny nie. W związku z tym DFA jest minimalny wtedy i tylko wtedy, gdy wszystkie stany są rozróżnialne.
Algorytm 3
Step 1 - Wszystkie stany Q są podzielone na dwie partycje - final states i non-final states i są oznaczone P0. Wszystkie stany w partycji są równoważne zeru . Weź licznikk i zainicjuj go wartością 0.
Step 2- Przyrost k o 1. Dla każdego podziału w P k podziel stany w P k na dwie partycje, jeśli są one k-rozróżnialne. Dwa stany w tej partycji X i Y są k-rozróżnialne, jeśli jest wejścieS takie że δ(X, S) i δ(Y, S) są (k-1) -odróżnialne.
Step 3- Jeśli P k ≠ P k-1 , powtórz krok 2, w przeciwnym razie przejdź do kroku 4.
Step 4- Połącz k- ty równoważne zestawy i uczyń je nowymi stanami zredukowanego DFA.
Przykład
Rozważmy następujący DFA -
q | δ (q, 0) | δ (q, 1) |
---|---|---|
za | b | do |
b | za | re |
do | mi | fa |
re | mi | fa |
mi | mi | fa |
fa | fa | fa |
Zastosujmy powyższy algorytm do powyższego DFA -
- P 0 = {(c, d, e), (a, b, f)}
- P 1 = {(c, d, e), (a, b), (f)}
- P 2 = {(c, d, e), (a, b), (f)}
Stąd P 1 = P 2 .
Istnieją trzy stany w zredukowanym DFA. Obniżony DFA jest następujący -
Q | δ (q, 0) | δ (q, 1) |
---|---|---|
(a, b) | (a, b) | (c, d, e) |
(c, d, e) | (c, d, e) | (fa) |
(fa) | (fa) | (fa) |