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)