Języki, automaty i obliczenia/Ćwiczenia 5: Algorytmy konstrukcji automatu minimalnego

From Studia Informatyczne

Ćwiczenia 5

Ćwiczenie 1

Ile co najmniej stanów ma automat akceptujący dokładnie jedno słowo w o długości n?

Rozwiązanie

Minimalny automat akceptujący słowo a_1...a_n ma n+2 stany.

<flash>file=ja-lekcja05-c-rys1.swf|width=250|height=200</flash>

Rysunek 1

Ćwiczenie 2

Niech n \in \mathbb{N}_0 będzie dowolną, ustaloną liczbą. Wykaż, że automat rozpoznający język

L=\left\{ a^{k}b^{k}:0\leq k\leq n\right\}

ma co najmniej 2n+2 stany.

Rozwiązanie

Automat

<flash>file=ja-lekcja05-c-rys2.swf|width=350|height=250</flash>

Rysunek 2

akcepuje język L i jest automatem minimalnym (jego minimalizacja daje automat izomorficzny, wszystkie klasy są jednoelementowe).

Ćwiczenie 3

Niech \mathcal{B}=(S \slash \equiv, A, f', [s_0], T) będzie automatem minimalnym dla automatu \mathcal{A}=(S, A, f, s_0, T). Czy zbiór stanów S \slash \equiv automatu minimalnego obliczonego za pomocą algorytmu wyznaczania stanów rozróżnialnych, zależy od:

(1) wyboru w \mathcal{A} stanu początkowego s_0,
(2) wyboru w \mathcal{A} zbioru stanów końcowych T?

Rozwiązanie punktu 1

Nie. Wynika to bezpośrednio z analizy algorytmu. Relacja \equiv nie rozróżnia stanów ze względu na stan początkowy. Stan początkowy nie jest w żaden sposób wyróżniony w algorytmie podczas konstrukcji zbioru S \slash \equiv.

Rozwiązanie punktu 2

Tak, gdyż postać relacji \equiv zależy od tego jakie pary stanów są zaznaczone jako stany rozróżnialne, a w liniach 3. i 4. algorytmu, początkowe wyznaczenie stanów rozróżnialnych jest zależne od postaci zbioru T.

Ćwiczenie 4

Zastosuj algorytm wyznaczający stany rozróżnialne do

zminimalizowania następujących automatów:


Rysunek 3


Rysunek 4

Rozwiązanie punktu 1

Po wypełnieniu tabelki stwierdzamy, że s_1 \equiv s_2, s_3 \equiv s_4 oraz s_5 \equiv s_6, zatem automat

minimalny ma 3 stany: [s_1, s_2], [s_3, s_4] oraz [s_5, s_6].

Wskazówka do punktu 2

Zauważ, że stany s_1, s_3, s_5, s_6 i s_7 są równoważne. Przed rozpoczęciem algorytmu "sklej" je w jeden stan tak, aby uprościć automat, który będziesz minimalizował. W ten sposób zamiast minimalizować automat 10-stanowy, będziesz minimalizował automat o 6 stanach.

Rozwiązanie punktu 2

Sklejmy stany s_1, s_3, s_5, s_6, s_7 w jeden stan (od razu widać, że są równoważne) i powstały w ten sposób stan oznaczmy jako s_0. Po wypełnieniu tabelki okazuje się, że wszystkie jej pola są wypełnione X-ami. Zatem każde dwa spośród stanów s_0, s_2, s_4, s_8, s_9, s_{10} są rozróżnialne. Automat minimalny posiada więc 6 stanów.

Ćwiczenie 5

Wykorzystując algorytm stabilizujących się relacji wyznacz automaty minimalne dla automatów z rysunków 3 oraz 4.

Ćwiczenie 6

Niech L=A^*aA^*bA^*, gdzie A=\{a,b\}. Zastosuj algorytm wykorzystujący pochodną Brzozowskiego do obliczenia automatu minimalnego dla tego języka.

Rozwiązanie

Obliczamy zgodnie z algorytmem kolejne pochodne zaczynając od języka L. Dla uproszczenia oznaczmy X = L \cup A^*bA^* = A^*aA^*bA^* \cup A^*bA^*, Y = X \cup A^* = A^*.

\begin{array}{rlll}a^{-1}L & = & a^{-1}(A^*aA^*bA^*) = A^*aA^*bA^* \cup A^*bA^* = X\\ b^{-1}L & = & b^{-1}(A^*aA^*bA^*) = A^*aA^*bA^* = L\\ a^{-1}X & = & a^{-1}(A^*aA^*bA^*) \cup a^{-1}A^*bA^* = X \cup A^*bA^* = X\\ b^{-1}X & = & b^{-1}(A^*aA^*bA^*) \cup b^{-1}A^*bA^* = L \cup A^*bA^* \cup A^* = A^* = Y\\ a^{-1}Y & = & a^{-1}A^* = A^* = Y\\ b^{-1}Y & = & b^{-1}A^* = A^* =  Y \end{array}

Automat minimalny ma więc trzy stany, odpowiadające odpowiednio

językom L=A^*aA^*bA^*, X=A^*aA^*bA^* \cup A^*bA^* orazy Y=A^*. Stanem początkowym jest oczywiście stan L, natomiast stanem końcowym - stan Y (dlaczego?). Automat minimalny przedstawiony jest na rysunku 5.

<flash>file=ja-lekcja05-c-rys5.swf|width=250|height=200</flash>

Rysunek 5

Poniżej znajduje się opis jeszcze jednego algorytmu minimalizacji - algorytmu Hopcrofta. Jest on nieco bardziej skomplikowany niż trzy podane dotychczas algorytmy, ale posiada lepszą złożoność niż algorytm obliczania stanów rozróżnialnych czy też algorytm wyznaczania ciągu relacji stabilizujących. Przeanalizuj opis algorytmu i jego zapis, a następnie rozwiąż zadanie 7.

Algorytm Hopcrofta

Niech \mathcal{A}=(S,A,f,s_0,T) będzie automatem, a Q\subset S podzbiorem. Dowolny podzbiór R \subset S i dowolna litera a \in A wyznaczają na zbiorze Q relację równoważności o dwóch klasach abstrakcji:

Q_1=\{s \in Q : f(s,a) \in R\};\ Q_2=\{s \in Q : f(s,a) \not \in R\},

przy czym jeśli jeden ze zbiorów Q_1, Q_2 jest pusty, to relacja ta posiada tylko jedną klasę abstrakcji. Wprost z definicji zbiory Q_1 i Q_2 tworzą podział zbioru Q (tzn. Q=Q_1 \cup Q_2, \; Q_1 \cap Q_2= \emptyset).Oznaczmy omawianą relację przez \rho_R^a.

W algorytmie zmienna P oznacza podział zbioru stanów S, a \mathcal{L} - listę par (Y, a), które będą wykorzystane do definiowania kolejnych relacji \rho^a_Y.

Algorytm MinHopcroft - algorytm Hopcrofta minimalizacji automatu


 1  Wejście: \mathcal{A}=(S, A, f, s_0, T) - automat taki, że L=L(\mathcal{A})
 2  Wyjście: P - podział zbioru S przez prawą kongruencję automatową
 3  P \leftarrow \{T, S \backslash T\};           \trianglerightP jest zbiorem rozłącznych podzbiorów S
 4  if |T|<|S \backslash T| then
 5    for each a \in A do 
 6      włóż(\mathcal{L}, (T, a));   
 7    end for
 8  else 
 9    for each a \in A do
 10     włóż (\mathcal{L},(S \backslash T, a));   
 11   end for
 12  end if
 13  while \mathcal{L} \neq \emptyset do
 14   (Y, a) \leftarrow zdejmij (\mathcal{L});
 15   \mathcal{X} \leftarrow \{X \in P:\ |X \slash \rho^a_Y| = 2\};
 16   for each X \in \mathcal{X} do 
 17     for each b \in A do
 18       \{X_1, X_2\} \leftarrow X \slash \rho^a_Y;       \trianglerightX \slash \rho^a_Y zawiera dwie klasy abstrakcji
 19       P \leftarrow (P \backslash X) \cup X_1 \cup X_2;
 20       if (X, b) \in \mathcal{L} then
 21         \mathcal{L} \leftarrow \mathcal{L} \backslash (X, b);            \triangleright zdejmij z \mathcal{L} dokładnie parę (X, b) 
 22         włóż(\mathcal{L},(X_1,b));
 23         włóż(\mathcal{L},(X_2,b));
 24       else  
 25         if |X_1|<|X_2| then
 26           włóż(\mathcal{L},(X_1,b));
 27         else
 28           włóż(\mathcal{L},(X_2,b)); 
 29         end if
 30       end if
 31     end for 
 32   end for 
 33  end while
 34  return P;


Funkcja zdejmij(\mathcal{L}) pobiera z listy \mathcal{L} dowolny element i zwraca go jako swoją wartość. Procedura włóż(\mathcal{L},X) dodaje do listy \mathcal{L} element X.

Aby zdefiniować funkcję przejść automatu minimalnego, jego zbiór stanów końcowych oraz stan początkowy, należy postąpić identycznie jak w algorytmie wyznaczania ciągu stabilizujących się relacji. Jedyna różnica polega na tym, że w miejsce relacji otrzymaliśmy podział zbioru S na klasy abstrakcji zadane przez poszukiwaną relację. Oczywiście klasy abstrakcji wyznaczają jednoznacznie relację równoważności i na odwrót - relacja równoważności wyznacza jednoznacznie podział zbioru na klasy równoważności, zatem forma opisu relacji przez klasy abstrakcji nie stanowi dla nas żadnego problemu.

Przy właściwej reprezentacji wszystkich używanych struktur, algorytm MinHopCroft działa w czasie |A|n \log n, gdzie n jest liczbą stanów automatu, a |A| rozmiarem jego alfabetu wejściowego. Wyjściem algorytmu jest podział P zbioru stanów. Każdy element zbioru P reprezentuje jeden stan automatu minimalnego.

Ćwiczenie 7

Zastosuj algorytm Hopcrofta do zminimalizowania automatu z rysunku 3 (patrz cwiczenie 4.)

Rozwiązanie

Na początku podział P dzieli S na P_1=\{s_1,s_2\} i P_2=\{s_3,s_4,s_5,s_6\}. Ponieważ |P_1|<|P_2| do pustej listy dodajemy (\{s_1,s_2\},a) oraz (\{s_1,s_2\},b).

Przechodzimy do pętli while (linia 5.). Zdejmujemy z

\mathcal{L} element (Y,a)=(\{s_1,s_2\},a). Dla każdego elementu X podziału P sprawdzamy, czy \rho_Y^a podzieli X.

\aligned\{s_1,s_2\} \slash \rho_{\{s_1,s_2\}}^a & = & \{s_1,s_2\}, \\ \{s_2,s_3,s_4,s_5,s_6\} \slash \rho_{\{s_1,s_2\}}^a & = & \{s_3,s_4,s_5,s_6\}. \\ \endaligned

Zdejmujemy z \mathcal{L} kolejny element, (Y,a) = (\{s_1,s_2\},b) . Obliczamy:

\aligned\{s_1,s_2\} \slash \rho_{\{s_1,s_2\}}^b & = & \{s_1,s_2\} \\ \{s_2,s_3,s_4,s_5,s_6\} \slash \rho_{\{s_1,s_2\}}^b & = & \{s_3,s_4\},\{s_5,s_6\} \\ \endaligned

Relacja \rho_{\{s_1,s_2\}}^b podzieliła zbiór \{s_3,s_4,s_5,s_6\}.
( f(s_3,b), f(s_4,b) \in \{s_1,s_2\}, f(s_5, b), f(s_6,b) \not \in \{s_1,s_2\}. )
P=\{s_1,s_2\}, \{s_3,s_4\}, \{s_5, s_6\}. Usuwamy (\{s_1,s_2\},b) z \mathcal{L}. Ponieważ na liście \mathcal{L} nie było ani elementu (\{s_3,s_4,s_5,s_6\},a), ani (\{s_3,s_4,s_5,s_6\},b), do listy dodajemy elementy (\{s_3,s_4\},a), (\{s_3,s_4\},b), (\{s_5,s_6\},a) oraz (\{s_5,s_6\},b).

Powracamy do początku pętli. Zdejmujemy z \mathcal{L} element

(Y,a)=(\{s_3,s_4\},a). Obliczamy:

\aligned\{s_1,s_2\} \slash \rho_{\{s_3,s_4\}}^a & = & \{s_1,s_2\} \\ \{s_3,s_4\} \slash \rho_{\{s_3,s_4\}}^a & = & \{s_3,s_4\} \\ \{s_5,s_6\} \slash \rho_{\{s_3,s_4\}}^a & = & \{s_5,s_6\} \\ \endaligned

\rho_{\{s_3,s_4\}}^a nie dzieli żadnego z elementów podziału P. Zdejmujemy więc z \mathcal{L} kolejny element, (Y,a)=(\{s_3,s_4\},b).
Sprawdź, że żadna z relacji: \rho_{\{s_3,s_4\}}^b, \rho_{\{s_5,s_6\}}^a, \rho_{\{s_5,s_6\}}^b nie utworzy nowego podziału.

(\{s_5,s_6\},b) jest ostatnim elementem listy i algorytm kończy działanie. Ostateczny podział zbioru S ma postać: \{s_1,s_2\}, \{s_3,s_4\}, \{s_5,s_6\}. Automat minimalny ma więc 3 stany, odpowiadające elementom podziału. Stanem początkowym jest stan \{s_3,s_4\}, a końcowym - stan \{s_1,s_2\}.

Otrzymaliśmy ten sam automat minimalny, co w zadaniu 4 (patrz cwiczenie 4.)

ZADANIA DOMOWE

Ćwiczenie 8

Zminimalizuj przedstawione poniżej automaty:

(1) stosując algorytm wyznaczający stany rozróżnialne,
(2) stosując algorytm stabilizujących się relacji,
(3) stosując algorytm Hopcrofta.


Rysunek 6


Rysunek 7


Ćwiczenie 9

Niech L=A^*aA^2, gdzie A=\{a,b\}. Zastosuj algorytm wykorzystujący pochodną Brzozowskiego do obliczenia automatu minimalnego dla tego języka.