Minimalizacja automatu
Kapitoly: Stany nieosiągalne, Stany nadmiarowe, Minimalizacja automatu
Przez minimalizację automatu rozumiemy znalezienie równoważnego automatu, który zawiera minimalną możliwą liczbę stanów. Nawet automat, który nie zawiera zbędnych stanów, może być dalej upraszczany.
Przykład
Rozważmy następujący automat:
Automat akceptuje tylko słowa 01 i 11. Jest oczywiste, że istnieje prostszy automat z trzema stanami, który akceptuje ten sam język. Stany q1 i q2 można połączyć w jeden nowy stan {q1, q2}, a te przejścia, które prowadziły do stanów q1 lub q2 będą prowadziły do nowego stanu, i to samo dla przejść pochodzących z q1 i q2. Otrzymujemy ten automat:
Ten automat najwyraźniej akceptuje ten sam język, co poprzedni, ale ma mniej stanów.
Równoważność stanów
Rozważmy automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$. Definiujemy język stanu q∈ Q, oznaczając L(q) jako
$$ L(q) = L(\left<Q, \Sigma, \delta, q, F\right>) $$
Oznacza to, że zmieniamy początkowy stan automatu A z q0 na q i obliczamy język akceptowany przez ten automat. Innymi słowy, w języku L(q) wszystkie słowa w są takie, że przechodzimy ze stanu q dla słowa w do stanu końcowego automatu A. Wracając do poprzedniego automatu, L(q1) = {1}.
Mówimy, że dwa różne stany q1 i q2 są równoważne, jeśli
$$ L(q_1) = L(q_2) $$
Co to oznacza? Jeśli stany q1, q2 są równoważne, to jeśli uczynimy je początkowymi stanami automatu, wygenerują one ten sam język. Innymi słowy, jeśli automat dotrze do konfiguracji <q1, w> i <q2, w>, musi zaakceptować lub odrzucić w obu przypadkach.
Wracając do poprzedniego automatu: stany q1 i q2 są równoważne, ponieważ jeśli jesteśmy w stanie q1, możemy zaakceptować słowo wejściowe tylko wtedy, gdy nieprzeczytana część słowa jest równa 1. To samo, jeśli jesteśmy w stanie q2.
Tak więc minimalizacja automatu polega na znalezieniu równoważnych stanów i usunięciu tych stanów poprzez połączenie ich w nowy stan, tak jak zrobiliśmy to w powyższym przykładzie.
Jak znaleźć równoważne stany
Jakie stany na pewno nie będą równoważne? Jeśli weźmiemy stan końcowy i stan niekońcowy, z pewnością nie będą one równoważne, ponieważ język stanu końcowego różni się od języka stanu niekońcowego - stan końcowy z pewnością akceptuje słowo $\varepsilon$, stan niekońcowy nie. Procedurę pokażemy od razu na przykładzie. Weźmy więc ten automat:
Zaczynamy od utworzenia dwóch zestawów 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 tworzymy tabelę przejść i przechowujemy informacje o grupach S1 i S2:
$$ \begin{array}{c|c|cc|c} \mbox{ Grupa }&\mbox{ Status }&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 zmodyfikujemy tabelę tak, aby zamiast bezpośrednio określać, do jakich stanów przechodzi dany symbol, po prostu odnotowujemy grupę, do której przechodzimy. Na przykład, ze stanu q3 dla 0 przechodzimy do stanu q5, który znajduje się w grupie S2. Więc zamiast q5 piszemy S2 w tabeli:
$$ \begin{array}{c|c|cc|c} \mbox{ Grupa }&\mbox{ Status }&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 dzielimy te dwie grupy. Zawsze umieszczamy stany, które trafiają do tych samych grup dla wszystkich symboli. Na przykład stany q3 i q6 nie będą w tej samej grupie, ponieważ ani dla 0, ani dla 1 nie należą do tej samej grupy. I odwrotnie, stany q1 i q2 będą w tej samej grupie, ponieważ oba stany nie przechodzą dla 0 i oba przechodzą do grupy S1 dla 1. Tworzy to nowe grupy:
$$ \begin{array}{c|c|cc|c} \mbox{ Grupa }&\mbox{ Status }&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} $$
Mamy te same przejścia w każdej grupie. Zaznaczamy nowo utworzone grupy i ponownie sprawdzamy, do której z tych nowych grup przechodzą stany:
$$ \begin{array}{c|c|cc|c} \mbox{ Grupa }&\mbox{ Status }&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 dokonujemy kolejnego podziału grup. Widzimy jednak, że nie możemy dokonać dalszego podziału, otrzymalibyśmy te same grupy - ponieważ stany q1 i q2 mają te same przejścia w grupach, ale są już w tej samej grupie i nie ma już stanu w grupie S4. Algorytm znajdowania równoważnych stanów został zakończony. Musimy tylko wybrać jeden stan z każdej grupy, usunąć pozostałe, a wszystkie stany, które doprowadziły do usuniętych stanów, doprowadzą do jednego stanu, który wybraliśmy.
W ten sposób możemy wybrać, aby nasz nowy automat miał stany q3, q6, q0, q1, q4 i usunąć stany q2 i q5. Wszystkie przejścia, które prowadziły do q2 będą teraz prowadzić do q1, a wszystkie stany, które prowadziły do q5 będą prowadzić do q4:
Procedura minimalizacji automatów
- Usuń nieosiągalne stany,
- usuń stany nadmiarowe,
- usuń stany równoważne.