Minimalizacja automatu
Kapitoly: Stany nieosiągalne, Stany zbędne, Minimalizacja automatu
Przez minimalizację automatu rozumiemy znalezienie równoważnego automatu, który ma najmniejszą możliwą liczbę stanów. Nawet automat, który nie ma żadnego stanu zbędnego, może dać się jeszcze uprościć.
Przykład
Weźmy taki automat:
Automat akceptuje tylko słowa 01 i 11. Od razu widać, że istnieje prostszy automat z trzema stanami, który akceptuje ten sam język. Stany q1 i q2 możemy połączyć w jeden nowy stan {q1, q2}: przejścia, które prowadziły do stanu q1 albo q2, będą prowadzić do nowego stanu, i tak samo przejścia wychodzące z q1 i q2 będą wychodzić z nowego stanu. Dostaniemy taki automat:
Ten automat oczywiście akceptuje ten sam język co poprzedni, a przy tym ma mniej stanów.
Równoważność stanów
Weźmy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Język stanu q∈ Q, oznaczany L(q), definiujemy jako
$$ L(q) = L(\left<Q, \Sigma, \delta, q, F\right>) $$
Czyli zmieniamy stan początkowy automatu A z q0 na q i patrzymy, jaki język akceptuje tak zmieniony automat. Innymi słowy, w języku L(q) są wszystkie słowa w takie, że w automacie A dla słowa w dostaniemy się ze stanu q do stanu akceptującego. Jeśli wrócimy do poprzedniego automatu, to L(q1) = {1}.
Powiemy, że dwa różne stany q1 i q2 są równoważne, jeśli zachodzi
$$ L(q_1) = L(q_2) $$
Co to znaczy? Jeśli stany q1, q2 są równoważne i zrobimy z nich stany początkowe automatu, to automat będzie akceptował ten sam język. Innymi słowy: jeśli automat znajdzie się w konfiguracji <q1, w> albo <q2, w>, to w obu przypadkach musi słowo zaakceptować albo w obu przypadkach odrzucić.
Wróćmy do poprzedniego automatu: stany q1 i q2 są równoważne, bo jeśli jesteśmy w stanie q1, to możemy zaakceptować słowo wejściowe tylko wtedy, gdy jego nieprzeczytana część jest równa 1. To samo zachodzi w stanie q2.
Przy minimalizacji automatu chodzi więc o to, żeby znaleźć stany równoważne i pozbyć się ich tak, że połączymy je w jeden nowy stan, tak jak zrobiliśmy to w przykładzie powyżej.
Jak znaleźć stany równoważne
Które stany na pewno nie będą równoważne? Stan akceptujący i stan nieakceptujący na pewno równoważne nie są, bo język stanu akceptującego jest różny od języka stanu nieakceptującego – stan akceptujący na pewno akceptuje słowo $\varepsilon$, a nieakceptujący nie. Postępowanie od razu pokażemy na przykładzie. Weźmy taki automat:
Zaczniemy od tego, że utworzymy dwa zbiory stanów
\begin{eqnarray} S_1&=&F=\left\{q_3, q_6\right\},\\ S_2&=&Q\setminus F=\left\{q_0, q_1, q_2, q_4, q_5\right\}. \end{eqnarray}
Teraz utworzymy tabelę przejść i zachowamy w niej informację o grupach S1 i S2:
$$ \begin{array}{c|c|cc|c} \mbox{grupa}&\mbox{stan}&0&1\\\hline S_1&q_3&q_5&q_4\\ &q_6&—&—\\\hline S_2&q_0&q_1&q_2\\ &q_1&—&q_3\\ &q_2&—&q_3\\ &q_4&q_6&—\\ &q_5&q_6&—\\ \end{array} $$
Teraz zmienimy tabelę: zamiast wpisywać do niej, do jakiego stanu przechodzimy dla danego symbolu, zanotujemy tylko grupę, do której przechodzimy. Na przykład ze stanu q3 dla 0 dostaniemy się do stanu q5, który jest w grupie S2. Zamiast q5 wpiszemy więc do tabeli S2:
$$ \begin{array}{c|c|cc|c} \mbox{grupa}&\mbox{stan}&0&1\\\hline S_1&q_3&S_2&S_2\\ &q_6&—&—\\\hline S_2&q_0&S_2&S_2\\ &q_1&—&S_1\\ &q_2&—&S_1\\ &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$
Teraz dalej podzielimy obie grupy. Do tej samej grupy dajemy zawsze stany, które dla wszystkich symboli przechodzą do tych samych grup. Na przykład stany q3 i q6 nie będą w tej samej grupie, bo ani dla 0, ani dla 1 nie przechodzą do tej samej grupy. Natomiast stany q1 i q2 będą w tej samej grupie, bo oba nie mają przejścia dla 0 i oba dla 1 przechodzą do grupy S1. Utworzymy więc nowe grupy:
$$ \begin{array}{c|c|cc|c} \mbox{grupa}&\mbox{stan}&0&1\\\hline &q_3&S_2&S_2\\\hline &q_6&—&—\\\hline &q_0&S_2&S_2\\\hline &q_1&—&S_1\\ &q_2&—&S_1\\\hline &q_4&S_1&—\\ &q_5&S_1&—\\ \end{array} $$
W każdej grupie mamy takie same przejścia. Nowo powstałe grupy oznaczymy i znowu sprawdzimy, do której z tych nowych grup prowadzą przejścia ze stanów:
$$ \begin{array}{c|c|cc|c} \mbox{grupa}&\mbox{stan}&0&1\\\hline S_1&q_3&S_5&S_5\\\hline S_2&q_6&—&—\\\hline S_3&q_0&S_4&S_4\\\hline S_4&q_1&—&S_1\\ &q_2&—&S_1\\\hline S_5&q_4&S_2&—\\ &q_5&S_2&—\\ \end{array} $$
W tym momencie powinniśmy grupy znowu podzielić. Widzimy jednak, że żadnego dalszego podziału zrobić już nie możemy, dostalibyśmy te same grupy – stany q1 i q2 mają co prawda takie same przejścia między grupami, ale już są w tej samej grupie i żadnego innego stanu w grupie S4 nie ma. Algorytm szukania stanów równoważnych się kończy. Z każdej grupy wystarczy wybrać jeden stan, pozostałe usuniemy, a wszystkie przejścia, które prowadziły do usuniętych stanów, będą prowadzić do tego jednego wybranego stanu.
Możemy więc wybrać, że nasz nowy automat będzie mieć stany q3, q6, q0, q1, q4, a stany q2 i q5 usuniemy. Wszystkie przejścia, które prowadziły do q2, będą teraz prowadzić do q1, a wszystkie przejścia, które prowadziły do q5, będą prowadzić do q4:
Jak zminimalizować automat
- Usuniemy stany nieosiągalne,
- usuniemy stany zbędne,
- połączymy stany równoważne (z każdej grupy zostawimy jeden).