Minimalizacja deterministycznych automatów skończonych

Wstęp

W tym wykładzie zajmiemy się problemem minimalizacji liczby stanów w deterministycznych automatach skończonych. Konstruując automaty skończone często możemy dość do kilu rozwiązań o różnej liczbie stanów. Jak znaleźć automat o najmniejszej możliwej liczbie stanów? W przypadku deterministycznych automatów skończonych znany jest efektywny algorytm przekształcający dowolny automat akceptujący dany język w automat o minimalnej liczbie stanów.

Zanim poznamy ten algorytm i udowodnimy jego poprawność, zobaczmy na przykładzie jak można zminimalizować liczbę stanów.

Przykład

Weźmy na początek niedeterministyczny automat skończony akceptujący te słowa (nad alfabetem {a,b}), które zawierają podsłowo aab.

Automat ten ma 4 stany, a więc odpowiadający mu automat potęgowy ma 16 stanów. Oczywiście możemy się ograniczyć do stanów osiągalnych, a tych jest 6.

Zauważmy, że możemy skleić ze sobą wszystkie stany akceptujące -- po ich osiągnięciu nie można już ich opuścić, a więc słowo musi zostać zaakceptowane.

Uzyskaliśmy automat deterministyczny o 4 stanach. Czy to jest minimum? Zastanówmy się ile stanów jest niezbędnych. Potrzebny jest jeden stan akceptujący, do którego wchodzimy, gdy wczytamy podsłowo aab. Dodatkowo potrzebujemy przynajmniej 3 inne stany. Możemy je rozróżnić m.inn. po najkrótszych słowach koniecznych do osiągnięcia stanu akceptującego. Dla stanu początkowego jest to oczywiście słowo aab. Dla stanu w jakim jesteśmy po wczytaniu a jest to ab, a dla stanu, w którym jesteśmy po wczytaniu aa jest to b. Razem uzyskujemy 4 stany, a więc nasz automat jest minimalny.

Dowód istnienia automatu minimalnego

Jak widać z powyższego przykładu niektóre stany w automacie deterministycznym mogą być sobie ,,równoważne'' i możemy je skleić. Natomiast badając, czy stany są równoważne powinniśmy zwrócić uwagę na to jakie słowa z danych stanów prowadzą do stanów akceptujących. Jeśli są tu jakieś różnice, to stanów nie możemy sklejać. Narazie są to mało precyzyjne intuicje, ale za chwilę sformalizujemy je.

Nadal jednak pozostaje otwarte pytanie, czy usunięcie stanów nieosiągalnych i sklejenie stanów ,,równoważnych'' prowadzi do jednego automatu minimalnego? Czy też zaczynając od różnych automatów możemy uzyskać różne automaty minimalne? Pokażemy, że dla każdego języka regularnego istnieje jeden (z dokładnością do izomorfizmu) minimalny deterministyczny automat skończony.

Definicja

Niech A będzie ustalonym językiem. Przez A/x oznaczamy język postaci:

$$A/x = \{ y \in \Sigma^* : xy \in A \}$$

Języki postaci A/x dla $x \in \Sigma^*$ nazywamy językami ilorazowymi.

Inaczej mówiąc, A/x to język złożony ze wszystkich tych ciągów dalszych, które uzupełniają wystąpienia prefiksów x w słowach z A. W szczególności $A/\varepsilon = A$. Wprost z definicji języka A/x wynika następujący fakt:

Stąd zaś wynika kolejny fakt:

Jest tak gdyż:

A/xz = (A/x)/z = (A/y)/z = A/yz

Jeżeli dodatkowo A jest regularny to pojawiają się dodatkowe intuicje. Niech $M = \angles{Q, \Sigma, \delta, s, F}$ będzie deterministycznym automatem skończonym akceptujący A, L(M) = A, w którym wszystkie stany są osiągalne. A/x to język złożony z tych słów, które prowadzą ze stanu $\delta^*(s,x)$ do stanów akceptujących, (czyli jest to język akceptowany przez automat postaci $\angles{Q,\Sigma,\delta, \delta^*(s,x), F})$. Ponieważ to, jakie słowa prowadzą z danego stanu do stanów akceptujących zależy od tego stanu, ale nie od tego jak dostaliśmy się do tego stanu, więc zachodzi następujący fakt:

Możemy więc każdemu stanowi q automatu M przyporządkować jeden z języków ilorazowych A/x języka A -- dokładnie taki, dla którego $\delta^*(s,x) = q$. Wynika stąd kolejny fakt:

Okazuje się, że odwrotna implikacja jest również prawdziwa.

Dowód:

Implikacja w jedną stronę wynika z poprzedniego faktu. Musimy pokazać, że jeżeli istnieje skończenie wiele języków ilorazowych języka A, to A jest regularny. Skonstruujemy deterministyczny automat skończony akceptujący A. Stanami tego automatu będą języki ilorazowe języka A, $Q = \{A/x : x \in \Sigma^*\}$. Nasz automat skonstruujemy tak, że każdy stan jako język będzie zawierał dokładnie te słowa, które z tego stanu prowadzą do stanów akceptujących:

$$A/x = \{y \in \Sigma^* : \delta^*(A/x, y) \in F$$

Stanem początkowym jest oczywiście $A = A/\varepsilon$, gdyż nasz automat ma akceptować właśnie język A. Stanami akceptującymi są te stany, które jako języki zawierają słowo puste,

$$F = \{A/x : \varepsilon \in A/x\}$$

Czyli:

$$F = \{A/x : x \in A\}$$

Natomiast funkcja przejścia jest postaci:

$$\delta (A/x, a) = A/xa$$

Powyższa definicja jest poprawna, gdyż jeśli A/x = A/y, to A/xa = A/ya.

Trzeba jeszcze pokazać, że automat $M = \angles{Q,\Sigma,\delta, A, F}$ akceptuje język A. Niech $y \in \Sigma^*$, $y = a_1a_2 \dots a_k$. Zauważmy, że:

$$\begin{eqnarray*} \delta^*(A/x,y) &=& \delta^*(A/x,a_1a_2 \dots a_k) = &=& ... ... \dots a_k, \varepsilon) = &=& A/xa_1, a_2 \dots a_k = A/xy \end{eqnarray*}$$

Stąd, język akceptowany przez M to:

$$\begin{eqnarray*} L(M) &=& \{ x \in \Sigma^* : \delta^*(A, x) \in F \} = &=... ...epsilon \in A/x \} = &=& \{ x \in \Sigma^* : x \in A \} = A \end{eqnarray*}$$

Konstrukcja automatu minimalnego

Zauważmy, że automat skonstruowany w powyższym dowodzie ma minimalną liczbę stanów -- gdyż ma ich dokładnie tyle ile jest języków ilorazowych języka A. Pokażemy jak z dowolnego deterministycznego automatu skończonego akceptującego język A zrobić automat izomorficzny ze skonstruowanym powyżej.

Niech $M = \angles{Q, \Sigma, \delta, s, F}$ będzie dowolnym ustalonym deterministycznym automatem skończonym akceptującym język A, L(M) = A, w którym wszystkie stany są osiągalne. (Jeśli M zawiera stany nieosiągalne, to najpierw je usuwamy.) Każdemu stanowi $q \in Q$ możemy przypisać język złożony z tych słów, które prowadzą z q do stanów akceptujących. Język taki to A/x, gdzie x prowadzi z s do q, $\delta^*(s,x) = q$.

Niech $M_{/\approx}$ będzie automatem powstałym z M przez sklejenie ze sobą stanów, którym przypisaliśmy takie same języki ilorazowe. Ściśle rzecz biorąc, na stanach automatu M definiujemy relację równoważności $\approx \subseteq Q \times Q$ określoną w następujący sposób:

$$p \approx q \mathrm{ w.t.w. } \forall_{x \in \Sigma^*} \delta^*(p,x) \in F \equivalent \delta^*(q,x) \in F$$

Inaczej mówiąc, niech A/x i A/y będą językami ilorazowymi przypisanymi stanom p i q, wówczas $p \approx q$ wtw., gdy A/x = A/y.

Sklejamy te stany automatu M, które są sobie równoważne:

$$M_{/\approx} = \angles{ Q_{/\approx}, \Sigma, \delta_{/\approx}, [s]_\approx, F_{/\approx} }$$

gdzie:

$$\delta_{/\approx}([q]_\approx, a) = [\delta(q,a)]_\approx$$

Automat $M_{/\approx}$ jest nazywany automatem ilorazowym.

Po pierwsze musimy się upewnić, czy $\delta_{/\approx}$ jest poprawnie zdefiniowana. Musimy w tym celu pokazać, że jeżeli sklejamy ze sobą dwa stany $p, q \in Q$, $p \approx q$, to dla dowolnego $a \in \Sigma$ mamy również $\delta(p,a) \approx \delta(q,a)$. Skoro $p \approx q$, to A/x = A/y, a zatem A/xa = A/ya, czyli $\delta(p,a) \approx \delta(q,a)$.

Zauważmy, że nigdy nie skleimy stanu akceptującego z nieakceptującym, gdyż stany akceptujące charakteryzują się tym, że przypisane im języki zawierają słowa puste.

Czy automat $M_{/\approx}$ akceptuje ten sam język co M, $L(M_{/\approx}) = L(M)$? Można pokazać (przez indukcję), że dla dowolnego stanu $q \in Q$ i słowa $x \in \Sigma^*$ mamy $\delta_{/\approx}^*([q]_\approx, x) = [\delta^*(q, x)]_\approx$. Ponieważ jednak nie skleiliśmy żadnego stanu akceptującego z żadnym ze stanów nieakceptujących, mamy:

$$\begin{eqnarray*} L(M_{/\approx}) &=& \{x \in \Sigma^* : \delta_{/\approx}^... ... &=& \{x \in \Sigma^* : \delta^*(s, x) \in F \} = L(M) = A \end{eqnarray*}$$

Tak więc usuwając stany nieosiągalne i sklejając ze sobą stany, którym odpowiadają te same języki ilorazowe otrzymujemy ten sam minimalny deterministyczny automat skończony akceptujący dany język regularny.

Przykład

Weźmy następujący automat deterministyczny:

Stan p jest nieosiągalny. Po jego usunięciu mamy:

Tylko dwa stany możemy skleić ze sobą: r i q, $r \approx q$. Po ich sklejeniu uzyskujemy;

Algorytm minimalizacji

Pokażemy jak można zaimplementować opisaną w poprzednim punkcie konstrukcję. Algorytm minimalizacji składa się z dwóch faz:

1. usunięcia stanów nieosiągalnych,
2. wyznaczenia relacji równoważności $\approx$ i sklejenia ze sobą stanów równoważnych.

Znalezienie stanów nieosiągalnych jest prostsze. Trudniej natomiast znaleźć stany równoważne. Przypomnijmy, że dwa stany p i q są sobie równoważne, gdy:

$$\forall_{x \in \Sigma^*} \delta^*(p,x) \in F \equivalent \delta^*(q,x) \in F$$

Pokażemy algorytm, który znajduje wszystkie pary nierównoważnych sobie stanów. Siłą rzeczy, pozostałe pary stanów są sobie równoważne i można je skleić ze sobą.

Jeśli stany p i q nie są sobie równoważne, to istnieje rozróżniające je słowo x, takie że:

$$\delta^*(p,x) \in F \not \equivalent \delta^*(q,x) \in F$$

Początkowo zakładamy, że wszystkie stany można skleić ze sobą. Następnie sukcesywnie wyznaczamy pary stanów które nie są sobie równoważne -- w kolejności wg. rosnącej długości najkrótszych rozróżniających je słów.

Algorytm

1. Tworzymy tablicę wartości logicznych T_{p,q} indeksowaną nieuporządkowanymi parami {p,q} stanów $p, q \in Q$. Początkowo T_{p,q} = true dla wszystkich $p, q \in Q$.
2. Dla wszystkich takich par stanów {p,q}, że $p \in F$ i $q \not\in F$ zaznaczamy T_{p,q} = false. Jeśli p jest akceptujący, a q nie, to stany te rozróżnia słowo puste $\varepsilon$.
3. Dla wszystkich par stanów {p,q} i znaków $a \in \Sigma$ takich, że $T_{\{\delta(p,a),\delta(q,a)\}} = \mathtt{false}$, zaznaczamy również T_{p,q} = false.
4. Jeżeli w kroku 3 zmieniliśmy choć jedną komórkę tablicy T z true na false, to powtarzamy krok 3 -- tak długo, aż nie będzie on powodował żadnych zmian w tablicy T.
5. Na koniec mamy: $p \approx q \equivalent T_{\{p,q\}}$.

Dowód poprawności algorytmu:

Poprawność algorytmu wynika stąd, że dla każdej pary stanów {p,q}, które nie są sobie równoważne istnieje pewne słowo, które je rozróżnia. Weźmy najkrótsze takie słowo. W kroku 2 wyznaczamy wszystkie takie pary, które są rozróżniane przez $\varepsilon$. Z każdym powtórzeniem kroku 3 wyznaczamy wszystkie takie pary, które są rozróżniane przez słowa o jeden dłuższe.

Ponieważ tablica T ma skończoną liczbę komórek, więc krok 3 jest powtarzany ograniczoną liczbę razy, a powyższy algorytm zawsze się zatrzyma.

Przykład

Weźmy następujący automat deterministyczny:

Wszystkie stany są osiągalne. Tablica T obliczona dla tego automatu uzyskuje swą postać już w kroku 2:

$$\begin{array}{cccc} \cline{1-1} \multicolumn{1}{\vert c\v... ...} & \multicolumn{1}{\vert c\vert}{s} \hline \end{array}$$

Co oznacza, że możemy skleić ze sobą stany s i q oraz p i r:

Przykład

Weźmy następujący automat deterministyczny:

Stan 0 jest nieosiągalny. Po jego usunięciu mamy:

Tablica T obliczona dla tego automatu uzyskuje swą ostateczną postać po jednokrotnej iteracji kroku 3:

$$\begin{array}{ccccccc} \cline{1-1} \multicolumn{1}{\vert ... ... \multicolumn{1}{\vert c\vert}{7} \cline{1-7} \end{array}$$

Co oznacza, że możemy skleić ze sobą stany: 2 z 3, 4 z 5, oraz 6 z 7.

Podsumowanie

W tym wykładzie poznaliśmy (uproszczone) twierdzenie Myhilla-Nerode'a. Twierdzenie to dostarcza nam jeszcze jednego kryterium do badania czy języki są regularne -- każdy język regularny ma skończenie wiele języków ilorazowych. Jako wniosek z dowodu tego twierdzenia uzyskaliśmy, że istnieje jeden (z dokładnością do izomorfizmu) minimalny automat deterministyczny akceptujący dany język. Poznaliśmy też algorytm wyznaczania tego minimalnego automatu.

Skorowidz

• Automat ilorazowy to minimalny deterministyczny automat skończony powstały przez sklejenie stanów równoważnych (zgodnie z daną relacją równoważności na stanach, spełniającą pewne dodatkowe warunki).

• Algorytm minimalizacji deterministycznych automatów skończonych -- algorytm wyznaczania minimalnego deterministycznego automatu skończonego na podstawie dowolnego deterministycznego automatu skończonego akceptującego dany język.

• Język ilorazowy języka A, to każdy z języków postaci $A/x = \{ y \in \Sigma^* : xy \in A \}$ (dla $x \in \Sigma^*$).

Praca domowa

Zminimalizuj następujące deterministyczne automaty skończone:

1. (4p.)
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 1 &... ... 3 \\ 2 & 1 & 4 \\ F3 & 1 & 1 \\ F4 & 1 & 1 \end{array}$$
   
   

2. (6p.)
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to F1 ... ... & 5 \\ 4 & 1 & 6 \\ 5 & 1 & 2 \\ 6 & 4 & 1 \end{array}$$
   
   

Ćwiczenia

Zminimalizuj następujące deterministyczne automaty skończone:

1.   
   
   Rozwiązanie
   
   zamknij

2. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to1 & 3 & 4 \\ 2 & 4 & 3 \\ F3 & 2 & 1 \\ F4 & 1 & 2 \end{array}$$
   
   

3. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 1 &... ...& 3 \\ 4 & 3 & 1 \\ F5 & 1 & 5 \\ 6 & 5 & 2 \end{array}$$
   
   

4. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to1 & 4 & 2 \\ F2 & 3 & 2 \\ 3 & 4 & 2 \\ F4 & 4 & 3 \end{array}$$
   
   
   Rozwiązanie
   Możemy skleić stany 1 i 3.
   

   $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline \to 1,3 & 4 & 2 \\ F2 & 1,3 & 2 \\ F4 & 4 & 1,3 \end{array}$$

   
   

   
   zamknij

5. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to F1 ... ...& 1 \\ 2 & 3 & 2 \\ F3 & 4 & 3 \\ 4 & 1 & 4 \end{array}$$
   
   
   Rozwiązanie
   Możemy skleić stany 1 i 3, oraz 2 i 4.
   

   $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline \to F1,3 & 2,4 & 1,3 \\ 2,4 & 1,3 & 2,4 \end{array}$$

   
   

   
   zamknij

6. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 1 & 3 & 4 \\ 2 & 4 & 3 \\ 3 & 4 & 1 \\ F4 & 1 & 3 \end{array}$$
   
   
   Rozwiązanie
   Stan 2 nie jest osiągalny i można go pominąć.
   

   $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline \to 1 & 3 & 4 \\ 3 & 4 & 1 \\ F4 & 1 & 3 \end{array}$$

   
   

   
   zamknij

7. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 1 &... ... & 4 \\ 4 & 5 & 1 \\ 5 & 1 & 4 \\ 6 & 5 & 1 \end{array}$$
   
   
   Rozwiązanie
   Stan 2 jest nieosiągalny. Stany 4 i 6 można skleić.
   

   $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline \to ... ... F3 & 5 & 4,6 \\ 4,6 & 5 & 1 \\ 5 & 1 & 4,6 \end{array}$$

   
   

   
   zamknij

8. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline 1 & 2 &... ...& 3 \\ 4 & 5 & 1 \\ F5 & 2 & 4 \\ 6 & 5 & 6 \end{array}$$
   
   
   Rozwiązanie
   Stan 6 jest nieosiągalny. Można skleić stany 1,3 i 4, oraz 2 i 5.
   

   $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline \to 1,3,4 & 2,5 & 1,3,4 \\ F2,5 & 2,5 & 1,3,4 \end{array}$$

   
   

   
   zamknij

9. 
   
   $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 1 &... ...& 1 \\ 4 & 1 & 6 \\ 5 & 6 & 1 \\ F6 & 5 & 3 \end{array}$$
   
   
   Rozwiązanie
   Stany 2 i 4 są nieosiągalne. Można skleić stany 3 i 5.
   

   $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline \to 1 & 6 & 6 \\ 3,5 & 6 & 1 \\ F6 & 3,5 & 3,5 \end{array}$$

   
   

   
   zamknij

10. 
    
    $$\begin{array}{r\vert c\vert c} & a & b\\ \hline 0 & 4 &... ... 6\\ 4 & 0 & 0\\ \to 5 & 3 & 1\\ F6 & 5 & 4 \end{array}$$
    
    
    Rozwiązanie
    Stan 2 jest nieosiągalny. Stany 0 i 4, oraz 1 i 3 można skleić.
    

    $$\begin{array}[t]{r\vert c\vert c} & a & b\\ \hline 0,4 ... ... & 0,4 & 6\\ \to 5 & 1,3 & 1,3\\ F6 & 5 & 0,4 \end{array}$$

    
    

    
    zamknij

11. 
    
    $$\begin{array}{r\vert c\vert c} & a & b\\ \hline 0& 2& 4... ... \to 3& 1& 5\\ 4& 6& 3\\ F5& 2& 5\\ 6& 6& 3 \end{array}$$
    
    

12. 
    
    $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 0 &... ... \\ 5 & 1 & 1 \\ 6 & 5 & 2 \\ 7 & 5 & 3 \\ \end{array}$$
    
    

13. 
    
    $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to 0 &... ...\\ F5 & 2 & 3 \\ 6 & 3 & 2 \\ 7 & 3 & 5 \\ \end{array}$$
    
    

14. 
    
    $$\begin{array}{r\vert c\vert c} & a & b\\ \hline \to F 1... ... & 7 \\ 5 & 4 & 3 \\ 6 & 3 & 6 \\ 7 & 3 & 1 \end{array}$$