Języki, automaty i obliczenia/Wykład 5: Algorytmy konstrukcji automatu minimalnego

W tym wykładzie podamy algorytmy konstrukcji automatu minimalnego i twierdzenia dowodzące ich poprawności.

Algorytmy konstrukcji automatu minimalnego

Dla języka rozpoznawanego $L$ konstrukcję automatu minimalnego można rozpocząć, startując z opisu języka danego na przykład przez wyrażenie regularne lub też jakiegoś automatu rozpoznającego ten język. W niniejszym wykładzie przedstawimy algorytmy konstrukcji automatu minimalnego obejmujące oba wspomniane punkty startu. Jako pierwszy, nawiązując do rezulatów przedstawionych w poprzednim wykładzie, prezentujemy algorytm, dla którego punktem wyjścia jest język $L$. Prezentację poprzedzimy wprowadzeniem pewnej operacji na słowach zwanej pochodną J.Brzozowskiego.

Definicja 1.1.

Niech $L\subset A^{*}$ będzie dowolnym językiem, a $u\in A^{*}$ dowolnym słowem. Pochodną Brzozowskiego (residuum) z języka $L$ względem słowa $u$ nazywamy język

$u^{-1}L=\{w\in A^{*}:uw\in L\}.$

Podczas obliczeń pochodnych Brzozowskiego (residuów języka $L$) można wykorzystać poniższe równości.

Niech $L_1,L_2\subset A^{*}$ będą dowolnymi językami, $a\in A$ dowolną literą, a $u,v\in A^{*}$ dowolnymi słowami. Prawdziwe są następujące równości:

Parser nie mógł rozpoznać (nieznana funkcja „\nonumber”): {\displaystyle \begin{array}{rll}\nonumber u^{-1}(L_1 \cup L_2) & = & u^{-1}L_1 \cup u^{-1}L_2, \\ \nonumber u^{-1}(L_1 \backslash L_2) & = & u^{-1}L_1 \backslash u^{-1}L_2, \\ \nonumber u^{-1}(L_1 \cap L_2) & = & u^{-1}L_1 \cap u^{-1}L_2, \\ \nonumber a^{-1}(L_1L_2) & = & (a^{-1}L_1)L_2 \mbox{, jeśli } 1 \notin L_1, \\ \nonumber a^{-1}(L_1L_2) & = & (a^{-1}L_1)L_2 \cup a^{-1}L_2 \mbox{, jeśli } 1 \in L_1, \\ \nonumber a^{-1}L^* & = & (a^{-1}L)L^*, \\ \nonumber v^{-1}(u^{-1}L) & = & (uv)^{-1}L. \end{array}}

Przykład 1.1.

Obliczmy wszystkie pochodne dla języka $L=a^{+}{b}^{+}$. Okazuje się, że są tylko cztery różne pochodne liczone względem $a$, $b$, $ab$ i słowa pustego $1$. Mianowicie:
$a^{-1}L=a^{*}{b}^{+}$,
$b^{-1}L=\mathrm{\varnothing }$,
$a{b}^{-1}L=b^{*}$,
$1^{-1}L=L$.
Dla wszystkich innych słów otrzymujemy uzyskane powyżej języki, co wynika z własności pochodnych (patrz wyżej wypisane równości) i z następujacych obliczeń:
$\mathrm{\forall }n\in \mathbb{\mathbb{N}}(a^n{)}^{-1}L=a^{*}{b}^{+}$,
$\mathrm{\forall }n\in \mathbb{\mathbb{N}}(b^n{)}^{-1}L=\mathrm{\varnothing }$,
$\mathrm{\forall }n\in \mathbb{\mathbb{N}}(a{b}^n{)}^{-1}L=b^{*}$.

Zauważmy również, nawiązując raz jeszcze do rezulatów przedstawionych w poprzednim wykładzie, że prawdziwa jest następująca równoważność wiążąca wprowadzone pojęcie pochodnej Brzozowskiego z prawą kongruencją syntaktyczną:

$uP{{}^r}_{L}v⟺u^{-1}L=v^{-1}L.$

Rozpisując z definicji lewą stronę tej równoważności, otrzymujemy, iż dla dowolnego słowa $z\in A^{*}$ słowo $uz\in L$ wtedy i tylko wtedy, gdy $vz\in L$. A to równoważnie oznacza (znów z definicji), że $u^{-1}L=v^{-1}L.$

Z uzasadnionej równoważności oraz twierdzenia 3.4 o prawej kongruencji syntaktycznej z poprzedniego wykładu wnioskujemy równoważność rozpoznawalności języka $L$ i skończonej ilości różnych pochodnych Brzozowskiego tego języka.

Pierwszy z przedstawianych algorytmów będzie konstruował automat minimalny, wyznaczając prawą kongruencję automatową poprzez zastosowanie metody pochodnych Brzozowskiego. Metoda ta umożliwia przeprowadzanie odpowiednich obliczeń bezpośrednio na wyrażeniach regularnych. Ogólny opis algorytmu jest następujący. Stany konstruowanego automatu minimalnego etykietowane są zbiorami odpowiadającymi pewnym językom. Mając dany język $L$, ustanawiamy stan początkowy automatu jako $L$, wpisujemy go na listę ${ℒ}$ i obliczamy $a^{-1}L$ dla każdej litery $a\in A$. Jeśli wśród obliczonych wartości znajduje się język niewystępujący na liście, dodajemy go do listy. Obliczenia pochodnych Brzozowskiego wykonujemy, dopóki będziemy uzyskiwać nowe języki (nowe stany). Funkcja przejść konstruowanego automatu minimalnego zdefiniowana jest następująco:

$f(X,a)=a^{-1}X,$

gdzie

$X$

jest pewnym językiem z listy

${ℒ}$

.

Obliczone języki określają stany automatu minimalnego.

Uwaga [Dla zainteresowanych]

Obliczone języki określające stany automatu minimalnego to elementy monoidu syntaktycznego języka $L$.

Automatem minimalnym dla automatu ${𝒜}=(S,A,f,s_0,T)$ będzie zatem automat

${{𝒜}}_L=(S_L,A,f_L,s_0^L,T_L),$

gdzie:

• $S_L=\{u^{-1}L:u\in A^{*}\}$,

• $s_0^L=L$,

• $T_L=\{u^{-1}L:u\in L\}$,

• $f_L(u^{-1}L,a)=a^{-1}(u^{-1}L)=(ua{)}^{-1}L$.

Jeśli zdefiniujmy odwzorowanie $\nu :S\to S_L$, kładąc:

$\nu (s)=u^{-1}L,\text{ gdzie }s=f(s_0,u),$

to można dowieść, że $\nu$ jest dobrze określone, jest epimorfizmem oraz $\nu (s_0)=s_0^L$ - porównaj twierdzenie 3.1 z wykładu 4. Prawdą jest też, iż $s\in T$ wtedy i tylko wtedy, gdy $\nu (s)\in T_L$ oraz że następujący diagram komutuje:

tutaj diagram

Formalny zapis algorytmu przedstawiony jest poniżej.

Algorytm Minimalizuj1 - algorytm minimalizacji wykorzystujący pochodne Brzozowskiego

---

  1  Wejście: ${𝒜}=(S,A,f,s_0,T)$ - automat taki, że $L=L({𝒜})$
  2  Wyjście: automat minimalny ${{𝒜}}^{\prime }=(S_L,A,f_L,s_L,T_L)$ dla ${𝒜}$
  3  $S_L\leftarrow \{L\}$;
  4  włóż$({ℒ},L)$;
  5  while ${ℒ}\ne \mathrm{\varnothing }$ do 
  6    $M\leftarrow$ zdejmij(${ℒ}$);   
  7    for each $a\in A$ do 
  8      $N\leftarrow a^{-1}M$;
  9      if $N\cap S_L=\mathrm{\varnothing }$ then
 10       $S_L\leftarrow S_L\cup \{N\}$;
 11       włóż$({ℒ},N)$;
 12     end if
 13    end for
 14  end  while  
 15  for each $M\in S_L$ do
 16    for each $a\in A$ do
 17      $f_L(M,a)\leftarrow a^{-1}M$;
 18    end for
 19  end for
 20  $s_L\leftarrow L$;
 21  $T_L\leftarrow \{u^{-1}L:u\in L\}$;
 22  return ${{𝒜}}^{\prime }$;

Funkcja zdejmij$({ℒ})$, występująca w linii 6., zdejmuje z kolejki ${ℒ}$ pierwszy element i zwraca go jako swoją wartość. Procedura włóż$({ℒ},L)$, występująca w liniach 4. oraz 11., wstawia na koniec kolejki ${ℒ}$ element $L$.

Przykład 1.2.

Dla języka $L=a^{+}{b}^{+}$ z przykładu 1.1 (patrz przykład 1.1.) w wyniku działania powyższego algorytmu otrzymamy czterostanowy automat ${{𝒜}}_L=(S_L,A,f,L,T),$ gdzie
$S_L=\{L,a^{*}{b}^{+},\mathrm{\varnothing },b^{*}\}$,

a funkcja przejść zadana jest grafem:

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

<div.thumbcaption>Rysunek 1

Prezentowane poniżej twierdzenie uzasadnia kolejny algorytm konstrukcji automatu minimalnego. Tym razem punktem wyjścia jest dowolny automat rozpoznający język $L$.

Uwaga [Dla zainteresowanych]

Algorytm oblicza również monoid syntaktyczny języka $L$.

Analogicznie do konstrukcji relacji ${\rho }_i$, przedstawionej w wykładzie 4, możemy określić ciąg odpowiednich relacji na zbiorze stanów dowolnego automatu rozpoznającego język $L$. Relacje te służą do efektywnego określenia automatu minimalnego, równoważnego zadanemu.

Twierdzenie 1.1.

Niech ${𝒜}=(S,A,f,s_0,T)$ będzie dowolnym automatem i niech $L=L({𝒜})$. Przez ${\approx }_{{𝒜}}\subset S\times S$ oznaczmy relację równoważności zawierającą dwie klasy równoważności $T$ i $S\setminus T$. Przez ${\bar{\rho }}_i$ dla $i\in \mathbb{\mathbb{N}}$ oznaczmy zstępujący ciąg relacji określony następująco:

${\bar{\rho }}_1={\approx }_{{𝒜}}$, a dla $i=2,...$ przyjmijmy

${\bar{\rho }}_i=\{(s,t)\in S\times S:\mathrm{\forall }a\in A\cup \{1\}f(s,a){\bar{\rho }}_{i-1}f(t,a)\}.$.

Wtedy $\bigcap {\bar{\rho }}_i$ jest największą prawą kongruencją automatową zawartą w relacji ${\bar{\rho }}_1={\approx }_{{𝒜}}$ i automat minimalny ma postać

${{𝒜}}_L=(S/\bigcap {\bar{\rho }}_i,A,f^{*},[s_0],T/\bigcap {\bar{\rho }}_i)$.

Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia 3.3 z wykładu 4 (patrz twierdzenie 3.3. wykład 4).

Algorytm działajacy w oparciu o powyższe twierdzenie na podstawie zadanego automatu $A=(S,A,f,s_0,T)$, konstruuje efektywnie automat minimalny dla ${𝒜}$, obliczając ciąg relacji ${\rho }_1$. Proces konstrukcji przebiega w sposób iteracyjny. Zaczynamy od zdefiniowania relacji Parser nie mógł rozpoznać (nieznana funkcja „\mathacal”): {\displaystyle \approx _\mathacal {A}} , która posiada tylko dwie klasy abstrakcji: do pierwszej z nich należą wszystkie stany końcowe, a do drugiej - wszystkie pozostałe stany. Tak więc

$\mathrm{\forall }s,t\in Ss{\approx }_{{𝒜}}t\iff (s\in T\wedge t\in T)\vee (s\in S\mathrm{\setminus }T\wedge t\in S\mathrm{\setminus }T)$.

Definiujemy pierwszą z relacji $\bar{\rho }$, czyli relację ${\bar{\rho }}_1$ jako równą ${\approx }_{{𝒜}}$, a następnie, dla każdej obliczonej już relacji ${\bar{\rho }}_i-1$, obliczamy relację ${\bar{\rho }}_i$ w następujący sposób:

$s_1{\bar{\rho }}_i{s}_2\iff (s_1{\bar{\rho }}_{i-1}{s}_2)\wedge (\mathrm{\forall }a\in Af(s_1,a){\bar{\rho }}_{i-1}f(s_2,a))$.

Nowo obliczona relacja ${\bar{\rho }}_i$ albo podzieli jedną lub kilka klas abstrakcji relacji ${\bar{\rho }}_{i-1}$, albo będzie identyczna z relacją ${\bar{\rho }}_{i-1}$. Jeśli zajdzie ta druga sytuacja, to znaczy, że dla każdego $j>i$ w oczywisty sposób spełniona jest równość ${\bar{\rho }}_j={\bar{\rho }}_i$, czyli ciąg relacji ustabilizuje się. W tym momencie algorytm kończy swoje działanie i klasy abstrakcji relacji ${\bar{\rho }}_i$ będą reprezentować stany automatu minimalnego.

Algorytm Minimalizuj2 - algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji

---

  1  Wejście: ${𝒜}=(S,A,f,s_0,T)$ - automat taki, że $L=L({𝒜})$.
  2  Wyjście: automat minimalny ${{𝒜}}^{\prime }=(S^{\prime },A^{\prime },f^{\prime },{s_0}^{\prime },T^{\prime })$ dla ${𝒜}$.
  3  ${\bar{\rho }}_1\leftarrow {\approx }_{{𝒜}}$;
  4  $i\leftarrow 1$;
  5  repeat
  6    Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle \slash \slash}
 oblicz ${\bar{\rho }}_i$: $s_1{\bar{\rho }}_i{s}_2\iff (s_1{\bar{\rho }}_{i-1}{s}_2)\wedge (\mathrm{\forall }a\in Af(s_1,a){\bar{\rho }}_{i-1}f(s_2,a))$;
  7    $i\leftarrow i+1$;
  8    empty$({\bar{\rho }}_i)$ 
  9    for each $(s_1,s_2)\in S\times S$ do
 10      flag$\leftarrow$true;
 11      for each $a\in A$ 
 12        if not $f(s_1,a){\bar{\rho }}_{i-1}f(s_2,a)$ then
 13          flag$\leftarrow$false;
 14        end if
 15      end for
 16      if flag=true and $s_1{\bar{\rho }}_{i-1}{s}_2$ then
 17        ${\bar{\rho }}_i\leftarrow {\bar{\rho }}_i\cup \{(s_1,s_2)\}$;
 18      end if
 19    end for
 20  until ${\bar{\rho }}_i={\bar{\rho }}_{i-1}$
 21  Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle S' \leftarrow S \slash \overline{\rho}_i}
;
 22  for each Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle [s]_{\overline{\rho}_i} \in S \slash \overline{\rho}_i}
 do
 23    for each $a\in A$ do
 24      $f^{\prime }([s{]}_{{\bar{\rho }}_i},a)\leftarrow [f(s,a){]}_{{\bar{\rho }}_i}$;
 25    end for
 26  end for
 27  ${s_0}^{\prime }\leftarrow [s_0{]}_{{\bar{\rho }}_i}$;
 28  $T^{\prime }\leftarrow \{[t{]}_{{\bar{\rho }}_i}:t\in T\}$;
 29  return ${{𝒜}}^{\prime }=(S^{\prime },A,f^{\prime },{s_0}^{\prime },T^{\prime })$;

Przykład 1.3.

Zminimalizujemy automat ${𝒜}=(S,A,f,s_0,T)$, dla którego
$S=\{s_0,s_1,s_2,s_3,s_4,s_5\},A=\{a,b\},T=\{s_1,s_2,s_4\}$ ,

a funkcja przejść określona jest przy pomocy grafu.

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

<div.thumbcaption>Rysunek 2

Konstruujemy ciąg relacji ${\bar{\rho }}_i$.

Na początku ${\bar{\rho }}_1$ dzieli $S$ na dwie klasy abstrakcji; pierwsza zawiera stany końcowe, a druga -- wszystkie pozostałe, czyli uzyskujemy dwa zbiory $\{s_1,s_2,s_4\}$ oraz $\{s_0,s_3,s_5\}$.

Obliczmy ${\bar{\rho }}_2$ (pierwszy przebieg pętli w liniach 5.-20. algorytmu). Aby dwa elementy (stany) $s$ i $t$ były ze sobą w relacji ${\bar{\rho }}_2$ muszą być ze sobą w relacji ${\bar{\rho }}_1$ oraz musi zachodzić

$\mathrm{\forall }a\in Af(s,a){\bar{\rho }}_{1}f(t,a).$

Czyli kolejna, nowa relacja może ewentualnie podzielić już istniejące zbiory zdefiniowane przez poprzednią relację. Nie może więc zajść taka sytuacja, że w jednej klasie abstrakcji relacji ${\bar{\rho }}_{i+1}$ znajdą się elementy z różnych klas abstrakcji relacji ${\bar{\rho }}_i$.

Rozważmy najpierw zbiór $\{s_1,s_2,s_4\}$. Oczywiście każde dwa stany z tego zbioru są ze sobą w relacji ${\bar{\rho }}_1$. Zauważmy, że $f(s_2,a)=f(s_4,a)=s_2$, $f(s_2,b)=f(s_4,b)=s_4$, więc $s_2{\bar{\rho }}_2{s}_4$ (bo $s_2{\bar{\rho }}_1{s}_2$ oraz $s_4{\bar{\rho }}_1{s}_4$). Ponieważ $f(s_1,b)=s_5$ i $f(s_2,b)=s_4$, a wiemy, że $s_5$ nie jest w relacji ${\bar{\rho }}_1$ z $s_4$, zatem stany $s_1$ i $s_2$ nie mogą być ze sobą w relacji ${\bar{\rho }}_2$, a to oznacza, że także stany $s_1$ i $s_4$ nie mogą być ze sobą w relacji ${\bar{\rho }}_2$.

W analogiczny sposób można sprawdzić, że relacja ${\bar{\rho }}_2$ nie podzieli zbioru $\{s_0,s_3,s_5\}$. Ostatecznie, po pierwszym wykonaniu pętli algorytmu minimalizacji obliczyliśmy relację ${\bar{\rho }}_2$, która dzieli $S$ na następujące podzbiory:

$\{s_1\},\{s_2,s_4\},\{s_0,s_3,s_5\}.$

W kolejnym kroku obliczamy ${\bar{\rho }}_3$. Zbiór $\{s_1\}$ oczywiście nie może być już podzielony na mniejsze podzbiory. Łatwo zauważyć, że ${\bar{\rho }}_3$ nie podzieli także zbioru $\{s_2,s_4\}$.

Rozważmy teraz zbiór $\{s_0,s_3,s_5\}$. Mamy $f(s_3,a)=f(s_5,a)$ oraz $f(s_3,b)=s_3$, $f(s_5,b)=s_5$ i wiadomo, że $s_3{\bar{\rho }}_2{s}_5$, zatem $s_3$ i $s_5$ będą ze sobą w relacji ${\bar{\rho }}_3$.

Ponieważ $f(s_0,a)=s_2$ i $f(s_3,a)=s_1$, ale $s_2$ i $s_1$ nie są ze sobą w relacji ${\bar{\rho }}_2$, zatem nie mogą być także ze sobą w relacji ${\bar{\rho }}_3$. Relacja ${\bar{\rho }}_3$ dzieli więc zbiór $\{s_0,s_3,s_5\}$ na zbiory $\{s_0\}$ oraz $\{s_3,s_5\}$.

Podział zbioru $S$ przez relację ${\bar{\rho }}_3$ wygląda więc

następująco:

$\{s_0\},\{s_1\},\{s_2,s_4\},\{s_3,s_5\}.$

Relacja ${\bar{\rho }}_4$ nie podzieli już ani zbioru $\{s_2,s_4\}$, ani zbioru $\{s_3,s_5\}$, więc uzyskujemy równość $\overline{{\rho }_4}={\bar{\rho }}_3$ i ponieważ ciąg relacji się ustabilizował, algorytm kończy działanie.

Podsumowując, mamy:

${\bar{\rho }}_1$

$\{s_1,s_2,s_4\},\{s_0,s_3,s_5\},$

${\bar{\rho }}_2$

$\{s_1\},\{s_2,s_4\},\{s_0,s_3,s_5\},$

${\bar{\rho }}_3$

$\{s_1\},\{s_2,s_4\},\{s_0\},\{s_3,s_5\}.{\bar{\rho }}_3={\bar{\rho }}_4$ i równoważny minimalny automat ${{𝒜}}_L=(S,f^{*},s_0,T)$ ma $4$ stany.

$q_0=\{s_0\},q_1=\{s_1\},q_2=\{s_2,s_4\},q_3=\{s_3,s_5\}$, $T=\{q_1,q_2\}$. Jak łatwo zauważyć jest to automat z przykładu 3.1 zamieszczonego w wykładzie 4 (patrz przykład 3.1. wykład 4). }}

<flash>file=ja-lekcja05-w-rys3.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 3

Jednym z najczęściej stosowanych algorytmów automatu minimalnego jest algorytm, który buduje "tabelkę" na podstawie której określa się automat minimalny. Poprawność tego algorytmu również uzasadnia twierdzenie 1.1 (patrz twierdzenie 1.1.).

W algorytmie tym wyznaczać będziemy tzw. stany rozróżnialne. Algorytm działa w czasie $O(|A|n^2)$, gdzie $|A|$ jest mocą alfabetu, a $n$ -- liczbą stanów automatu wejściowego, czyli podlegajacego minimalizacji. Złożoność pamięciowa jest również $O(|A|n^2)$. Prezentowany algorytm nosi nazwę algorytmu Hopcrofta-Ullmana. Znana w literaturze jest pewna zmodyfikowana wersja tego algorytmu. Jest to algorytm Aho-Sethiego-Ullmana, który ma tę samą złożoność czasową, ale lepszą złożoność pamięciową - $O(|A|n)$. Natomiast w ramach ćwiczeń prezentujemy jeszcze jeden algorytm, znany jako algorytm minimalizacji Hopcrofta. Czas działania tego algorytmu wynosi $O(n\log n)$.

Niech $\equiv$ będzie relacją zdefiniowaną przez funkcję przejść automatu w następujący sposób:

$p\equiv q\iff \mathrm{\forall }w\in A^{*}(f(p,w)\in T\iff f(q,w)\in T).$

Definicja 1.2.

Stany $p$ i $q$ są równoważne, jeśli $p\equiv q$.

Jeśli stany nie są równoważne, to będziemy mówić, że są rozróżnialne.

Zadaniem algorytmu jest wyznaczenie stanów równoważnych, celem ich utożsamienia ze sobą. Algorytm musi zdecydować, dla każdej pary stanów $(p,q)$, czy są one rozróżnialne. Jeśli pod koniec działania algorytmu okaże się, że nie stwierdziliśmy rozróżnialności tych stanów, to znaczy, że są one równoważne; następuje ich utożsamienie, czyli "połączenie" ich w jeden stan. Gdy takiego połączenia dokonamy dla wszystkich par stanów, wobec których nie stwierdziliśmy ich rozróżnialności, powstanie automat o minimalnej liczbie stanów.

W praktyce algorytm nie wyznacza stanów równoważnych, ale stany rozróżnialne, gdyż jest to po prostu łatwiejsze. Po wyznaczeniu wszystkich par stanów rozróżnialnych pozostałe pary stanowić będą stany równoważne.

W algorytmie wykorzystywać będziemy tablicę list ${ℒ}[p,q]$, po jednej liście dla każdej pary stanów. Funkcja initialize $({ℒ}[p,q])$ inicjalizuje listę pustą, funkcja zdejmij $({ℒ}[p,q])$ zdejmuje jeden z elementów, natomiast funkcja włóż $({ℒ}[p,q],x)$ wkłada element $x$ na listę ${ℒ}[p,q]$. Funkcja empty $({ℒ}[p,q])$ zwraca wartość true gdy lista jest pusta, oraz false w przeciwnym wypadku. Zwróćmy uwagę, że elementami każdej z list ${ℒ}[p,q]$ są pary stanów $(s,t)\in S\times S$.

Algorytm Minimalizuj3 - algorytm minimalizacji wykorzystujący relację $\equiv$

---

  1  Wejście: ${𝒜}=(S,A,f,s_0,T)$ - automat
  2  Wyjście: ${{𝒜}}^{\prime }=(S^{\prime },A,f^{\prime },{s_0}^{\prime },T^{\prime })$ - automat minimalny taki, że $L({{𝒜}}^{\prime })=L({𝒜})$.
  3  for each $p\in T$ do
  4    for each $q\in S\mathrm{\setminus }T$ do
  5      zaznaczone$[p,q]\leftarrow 1$;
  6      initialize(${ℒ}[p,q]$)
  7    end for
  8  end for
  9  for each $(p,q)\in (T\times T)\cup ((S\mathrm{\setminus }T)\times (S\mathrm{\setminus }T))$ do
 10    zaznaczone$[p,q]\leftarrow 0$;
 11  end for
 12  for each $(p,q)\in (T\times T)\cup ((S\mathrm{\setminus }T)\times (S\mathrm{\setminus }T))$ do
 13    flag$\leftarrow$false
 14    for each  $a\in A$ do
 15      if  zaznaczone$[f(p,a),f(q,a)]=1$ then
 16        flag$\leftarrow$true;
 17      end if
 18    end for
 19    if flag=true then
 20      OZNACZ$(p,q)$; $▹$ para $(f(p,a),f(q,a))$ była oznaczona dla pewnego $a$;
 21    else
 22      for each  $a\in A$ do
 23        if $f(p,a)\ne f(q,a)$ then
 24          włóż$({ℒ}[p,q],(f(p,a),f(q,a)))$;
 25        end if
 26      end for
 27    end if
 28  end for
 29  Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle S' \leftarrow S \slash_\equiv}
; $▹$ relacja $\equiv$ jest dopełnieniem tabeli zaznaczone
 30  for each Parser nie mógł rozpoznać (nieznana funkcja „\slash”): {\displaystyle \displaystyle [s]_{ \equiv} \in S \slash_\equiv}
 do
 31    for each $a\in A$ do
 32      $f^{\prime }([s{]}_{\equiv },a)\leftarrow [f(s,a){]}_{\equiv }$;
 33    end for
 34  end for
 35  ${s_0}^{\prime }\leftarrow [s_0{]}_{\equiv }$;
 36  $T^{\prime }\leftarrow \{[t{]}_{\equiv }:t\in T\}$;
 37  return ${{𝒜}}^{\prime }=(S^{\prime },A,f^{\prime },{s_0}^{\prime },T^{\prime })$;

Występujaca w algorytmie procedura Oznacz opisana jest poniżej.

Algorytm

---

 1  procedure OZNACZ$(p,q\in S)$
 2  if zaznaczone$[p,q]=1$ 
 3    return
 4  end if
 5  zaznaczone$[p,q]\leftarrow 1$
 6  while not empty$({ℒ}[p,q])$ do
 7    OZNACZ(zdejmij$({ℒ}[p,q]))$
 8  end while
 9  end procedure

Działanie algorytmu łatwo przedstawić na tabelce, która złożona jest z kwadratów - pól, odpowiadających parom stanów automatu. Fakt znalezienia przez algorytm pary stanów rozróżnialnych zaznaczamy symbolem "x" w polu tabelki odpowiadającym tej parze, co wykorzystamy w przykładzie.

Przykład 1.4.

Zminimalizujemy automat przedstawiony na rysunku 4, używając algorytmu Minimalizuj3.

<flash>file=ja-lekcja05-w-rys4.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 4

Proces działania algorytmu i konstrukcji tabelki przedstawiony jest na poniższej animacji 1.

TUTAJ ANIMACJA. ja-lekcja5-w-anim1.

Wypełniona tabelka po zakończeniu działania algorytmu przedstawiona jest na rysunku 5.

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

<div.thumbcaption>Rysunek 5

Z tabelki odczytujemy, że stanami równoważnymi są stany $s_1,s_5$, stany $s_2,s_8$ oraz stany $s_4,s_6$. Automat minimalny przedstawiony jest na rysunku 6.

<flash>file=ja-lekcja05-w-rys6.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 6