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

Ć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.

Rysunek 1

Ćwiczenie 2

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

$L=\{a^k{b}^k:0\le k\le n\}$

ma co najmniej $2n+2$ stany.

Rozwiązanie

Automat

Rysunek 2

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

Ćwiczenie 3

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

(1) wyboru w ${𝒜}$ stanu początkowego $s_0$,

(2) wyboru w ${𝒜}$ 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/\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^{*}a{A}^{*}b{A}^{*}$, 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^{*}b{A}^{*}=A^{*}a{A}^{*}b{A}^{*}\cup A^{*}b{A}^{*}$, $Y=X\cup A^{*}=A^{*}$.

$\begin{array}{rll}{a}^{-1}L& =& a^{-1}(A^{*}a{A}^{*}b{A}^{*})=A^{*}a{A}^{*}b{A}^{*}\cup A^{*}b{A}^{*}=X\\ b^{-1}L& =& b^{-1}(A^{*}a{A}^{*}b{A}^{*})=A^{*}a{A}^{*}b{A}^{*}=L\\ a^{-1}X& =& a^{-1}(A^{*}a{A}^{*}b{A}^{*})\cup a^{-1}{A}^{*}b{A}^{*}=X\cup A^{*}b{A}^{*}=X\\ b^{-1}X& =& b^{-1}(A^{*}a{A}^{*}b{A}^{*})\cup b^{-1}{A}^{*}b{A}^{*}=L\cup A^{*}b{A}^{*}\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^{*}a{A}^{*}b{A}^{*}$, $X=A^{*}a{A}^{*}b{A}^{*}\cup A^{*}b{A}^{*}$ 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.

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 ${𝒜}=(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)\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=\mathrm{\varnothing }$).Oznaczmy omawianą relację przez ${\rho }_R^a$.

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

Algorytm MinHopcroft - algorytm Hopcrofta minimalizacji automatu

---

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

Funkcja zdejmij(${ℒ}$) pobiera z listy ${ℒ}$ dowolny element i zwraca go jako swoją wartość. Procedura włóż(${ℒ},X$) dodaje do listy ${ℒ}$ 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 ${ℒ}$ element $(Y,a)=(\{s_1,s_2\},a)$. Dla każdego elementu $X$ podziału $P$ sprawdzamy, czy ${\rho }_Y^a$ podzieli $X$.

$\begin{array}{rlr}\{s_1,s_2\}/{\rho }_{\{s_1,s_2\}}^a& =& \{s_1,s_2\},\\ \{s_2,s_3,s_4,s_5,s_6\}/{\rho }_{\{s_1,s_2\}}^a& =& \{s_3,s_4,s_5,s_6\}.\\ \end{array}$

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

$\begin{array}{rlr}\{s_1,s_2\}/{\rho }_{\{s_1,s_2\}}^b& =& \{s_1,s_2\}\\ \{s_2,s_3,s_4,s_5,s_6\}/{\rho }_{\{s_1,s_2\}}^b& =& \{s_3,s_4\},\{s_5,s_6\}\\ \end{array}$

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)\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 ${ℒ}$. Ponieważ na liście ${ℒ}$ 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 ${ℒ}$ element $(Y,a)=(\{s_3,s_4\},a)$. Obliczamy:

$\begin{array}{rlr}\{s_1,s_2\}/{\rho }_{\{s_3,s_4\}}^a& =& \{s_1,s_2\}\\ \{s_3,s_4\}/{\rho }_{\{s_3,s_4\}}^a& =& \{s_3,s_4\}\\ \{s_5,s_6\}/{\rho }_{\{s_3,s_4\}}^a& =& \{s_5,s_6\}\\ \end{array}$

${\rho }_{\{s_3,s_4\}}^a$ nie dzieli żadnego z elementów podziału $P$. Zdejmujemy więc z ${ℒ}$ 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^{*}a{A}^2$, gdzie $A=\{a,b\}$. Zastosuj algorytm wykorzystujący pochodną Brzozowskiego do obliczenia automatu minimalnego dla tego języka.