Test GR

{theor}{TWIERDZENIE}[section] {rem}{UWAGA}[section] {corol}{WNIOSEK}[section] {fact}{FAKT}[section] {ex}{PRZYKŁAD}[section] {defin}{DEFINICJA}[section] {lem}{LEMAT}[section]

{prf}{DOWÓD}

{algorithm}{Algorytm}

{procedure}{Procedura}

{ Algorytmy konstrukcji automatu minimalnego }

Wprowadzenie

W tym wykładzie podamy algorytmy konstrukcji automatu minimalnego

i twierdzenia dowodzące ich poprawności.

Słowa kluczowe

automat minimalny, pochodna Brzozowskiego, algorytmy

minimalizacji.

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.

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 „\aligned”): {\displaystyle \aligned\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. \endaligned}

Ćwiczenie [Uzupelnij]

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.

---

dla dociekliwych - start ----

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

---

dla dociekliwych - end ----

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:

Parser nie mógł rozpoznać (nieznana funkcja „\beginCD”): {\displaystyle \beginCD s @>{a}>> s' @. \ \ \ \ \mbox{ w } \mathcal{A} \\ @V{\nu}VV @V{\nu}VV \\ u^{-1}L @>{a}>> (ua)^{-1}L @. \ \ \ \ \mbox{ w } \mathcal{A}_L. \endCD }

Formalny zapis algorytmu przedstawiony jest poniżej.

{{Minimalizuj1} - algorytm minimalizacji wykorzystujący pochodne Brzozowskiego} [1] Wejście: ${𝒜}=(S,A,f,s_0,T)$ - automat taki, że $L=L({𝒜})$

Wyjście: automat minimalny ${{𝒜}}^{\prime }=(S_L,A,f_L,s_L,T_L)$ dla ${𝒜}{S}_L\leftarrow \{L\}$;

włóż$({ℒ},L)$;

{${ℒ}=$}

$M\leftarrow$ zdejmij$({ℒ})$;

{each $a\in A$}

$N\leftarrow a^{-1}M$;

{$N\cap S_L=$ }

$S_L\leftarrow S_L\cup \{N\}$;

włóż$({ℒ},N)$;

{each $M\in S_L$}

{each $a\in A$}

$f_L(M,a)\leftarrow a^{-1}M$;

$s_L\leftarrow L$;

$T_L\leftarrow \{u^{-1}L:u\in L\}$;

${{𝒜}}^{\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$.

Ćwiczenie [Uzupelnij]

Dla języka $L=a^{+}{b}^{+}$ z przykładu 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:

RYSUNEK ja-lekcja5-w-rys1

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

---

dla dociekliwych - start -----

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

---

dla dociekliwych - end -----

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.

Niech

${𝒜}$

= (S,A,f,s_0,T)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będzie dowolnym automatem i niech } L=L({A})

$.Przez$

_Szablon:A S S Parser nie mógł rozpoznać (błąd składni): {\displaystyle oznaczmy relację równoważności zawierającą dwie klasy równoważności } T

$i$

S T

$.Przez$

{}_i

$dla$

i { N} Parser nie mógł rozpoznać (błąd składni): {\displaystyle oznaczmy zstępujący ciąg relacji określony następująco: } {}_1 = _Szablon:A

$,adla$

i = 2,...

$przyjmijmy$

{}_i = (s,t) S S  : a A 1 f(s,a) {}_{i-1} f(t,a) . Parser nie mógł rozpoznać (nieznana funkcja „\par”): {\displaystyle {\par\raggedright Wtedy } {}_i Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest największą prawą kongruencją automatową zawartą w relacji } {}_1 = _Szablon:A Parser nie mógł rozpoznać (błąd składni): {\displaystyle i automat minimalny ma postać\par} } {A}_{L}=( S/_{ { }_{i}},A,f^{*},[s_{0}],T/_{ { }_{i}}) .

Parser nie mógł rozpoznać (nieznana funkcja „\endtheor”): {\displaystyle \endtheor Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia 3.3 z wykładu 4. Algorytm działajacy w oparciu o powyższe twierdzenie na podstawie zadanego automatu } {A}=(S, A, f, s_0, T)$,konstruujeefektywnieautomatminimalnydla${A}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , obliczając ciąg relacji } {}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle . Proces konstrukcji przebiega w sposób iteracyjny. Zaczynamy od zdefiniowania relacji } _Szablon:AParser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 }

s, t Ss _Szablon:A t (s T t T) (s S T t S T).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Definiujemy pierwszą z relacji } {}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , czyli relację } {}_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle jako równą } _Szablon:AParser nie mógł rozpoznać (błąd składni): {\displaystyle , a następnie, dla każdej obliczonej już relacji } {}_{i-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , obliczamy relację } {}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle w następujący sposób: }

s_1 {}_i

s_2 (s_1 {}_{i-1} s_2) (

a Af(s_1, a) {}_{i-1} f(s_2,a)).

$Nowoobliczonarelacja${}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle albo podzieli jedną lub kilka klas abstrakcji relacji } {}_{i-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , albo będzie identyczna z relacją } {}_{i-1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli zajdzie ta druga sytuacja, to znaczy, że dla każdego } j>iParser nie mógł rozpoznać (błąd składni): {\displaystyle w oczywisty sposób spełniona jest równość } {_j}={}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle , czyli ciąg relacji ustabilizuje się. W tym momencie algorytm kończy swoje działanie i klasy abstrakcji relacji } {}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle będą reprezentować stany automatu minimalnego. \newpage \beginalgorithm \caption{\textsc{Minimalizuj2} -- algorytm minimalizacji automatu wykorzystujący stabilizujący się ciąg relacji} \beginalgorithmic [1] \STATE Wejście: } {A}=(S, A, f, s_0, T)Parser nie mógł rozpoznać (błąd składni): {\displaystyle -- automat taki, że } L=L({A})Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle . \STATE Wyjście: automat minimalny } {A}'=(S',A',f', s_0',

T')$dla${A}Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle . \STATE } {}_1_Szablon:AParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } i 1Parser nie mógł rozpoznać (nieznana funkcja „\REPEAT”): {\displaystyle ; \REPEAT \STATE oblicz } {}_i$:$s_1 {}_i s_2 (s_1 {}_{i-1} s_2) ( a Af(s_1, a) {}_{i-1} f(s_2,a))Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } i i+1Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE \textbf{empty}} ({}_i)Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle \FOR{\textbf{each} } (s_1,s_2) S SParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE flag\textbf{true}; \FOR{\textbf{each} } a AParser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle } \IF{\textbf{not} } f(s_1, a) {}_{i-1} f(s_2,a)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE flag\textbf{false}; \ENDIF \ENDFOR \IF{flag=\textbf{true} \textbf{and} } s_1 {}_{i-1} s_2Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } {}_{i} {}_{i} (s_1,s_2)Parser nie mógł rozpoznać (nieznana funkcja „\ENDIF”): {\displaystyle ; \ENDIF \ENDFOR \UNTIL{} {}_i = {}_{i-1}Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } S' S {}_iParser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle ; \FOR{\textbf{each} } [s]_{{}_i} S {}_iParser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle } \FOR{\textbf{each} } a AParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } f'([s]_{{}_i},a) [f(s,a)]_{{}_i}Parser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle ; \ENDFOR \ENDFOR \STATE } s_0' [s_0]_{{}_i}Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } T' [t]_{{}_i}:t TParser nie mógł rozpoznać (nieznana funkcja „\RETURN”): {\displaystyle ; \RETURN } {A}'=(S', A, f', s_0', T')Parser nie mógł rozpoznać (nieznana funkcja „\endalgorithmic”): {\displaystyle ; \endalgorithmic \endalgorithm {{cwiczenie|[Uzupelnij]|| Zminimalizujemy automat } {A}=(S,A,f,s_0,T)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , 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} Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a funkcja przejść określona jest przy pomocy grafu.\\ RYSUNEK ja-lekcja5-w-rys2\\ Konstruujemy ciąg relacji } {}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle . Na początku } {}_1$dzieli$SParser nie mógł rozpoznać (błąd składni): {\displaystyle 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${}_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle (pierwszy przebieg pętli w liniach 5.-20. algorytmu). Aby dwa elementy (stany) } s$i$tParser nie mógł rozpoznać (błąd składni): {\displaystyle były ze sobą w relacji } {}_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle muszą być ze sobą w relacji } {}_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle oraz musi zachodzić }

a A f(s, a) {}_1 f(t,a).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } {}_{i+1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle znajdą się elementy z różnych klas abstrakcji relacji } {}_iParser nie mógł rozpoznać (błąd składni): {\displaystyle . Rozważmy najpierw zbiór } s_1, s_2, s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Oczywiście każde dwa stany z tego zbioru są ze sobą w relacji } {}_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zauważmy, że } f(s_2, a)=f(s_4,a)=s_2$,$f(s_2,b)=f(s_4,b)=s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc } s_2 {}_2 s_4$(bo$s_2 {}_1 s_2$oraz$s_4 {}_1 s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle ). Ponieważ } f(s_1,b)=s_5$i$f(s_2,b)=s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a wiemy, że } s_5$niejestwrelacji${}_1$z$s_4$,zatemstany$s_1$i$s_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie mogą być ze sobą w relacji } {}_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a to oznacza, że także stany } s_1$i$s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie mogą być ze sobą w relacji } {}_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle . W analogiczny sposób można sprawdzić, że relacja } {}_2$niepodzielizbioru$s_0, s_3, s_5Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ostatecznie, po pierwszym wykonaniu pętli algorytmu minimalizacji obliczyliśmy relację } {}_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle , która dzieli } SParser nie mógł rozpoznać (błąd składni): {\displaystyle na następujące podzbiory: }

s_1, s_2, s_4, s_0, s_3, s_5.

$Wkolejnymkrokuobliczamy${}_3Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Zbiór } s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle oczywiście nie może być już podzielony na mniejsze podzbiory. Łatwo zauważyć, że } {}_3Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie podzieli także zbioru } s_2,

s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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_5Parser nie mógł rozpoznać (błąd składni): {\displaystyle i wiadomo, że } s_3 {}_2

s_5$,zatem$s_3$i$s_5Parser nie mógł rozpoznać (błąd składni): {\displaystyle będą ze sobą w relacji } {}_3Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ } f(s_0, a)=s_2$i$f(s_3, a)=s_1$,ale$s_2$i$s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie są ze sobą w relacji } {}_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle , zatem nie mogą być także ze sobą w relacji } {}_3$.Relacja${}_3Parser nie mógł rozpoznać (błąd składni): {\displaystyle dzieli więc zbiór } s_0, s_3, s_5$nazbiory$s_0$oraz$s_3, s_5Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Podział zbioru } SParser nie mógł rozpoznać (błąd składni): {\displaystyle przez relację } {}_3Parser nie mógł rozpoznać (błąd składni): {\displaystyle wygląda więc następująco: }

s_0, s_1, s_2, s_4, s_3, s_5.

$Relacja${}_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle nie podzieli już ani zbioru } s_2,

s_4$,anizbioru$s_3, s_5Parser nie mógł rozpoznać (błąd składni): {\displaystyle , więc uzyskujemy równość } {_4}={}_3Parser nie mógł rozpoznać (błąd składni): {\displaystyle i ponieważ ciąg relacji się ustabilizował, algorytm kończy działanie. Podsumowując, mamy:  ; } {} _{1}$:$s_1, s_{2},s_{4}, s_{0},s_{3},s_5, $;${} _{2}$:$s_{1},s_2,s_{4}, s_{0},s_{3},s_5,$;${} _{3}$:$s_{1},s_2,s_{4}, s_{0},s_{3},s_5.{} _{3}={} _{4}Parser nie mógł rozpoznać (błąd składni): {\displaystyle i równoważny minimalny automat } {A}_L=(S,f^*,s_0,T)$ma$4Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jak łatwo zauważyć jest to automat z przykładu 3.1 zamieszczonego w wykładzie 4. RYSUNEK ja-lekcja5-w-rys3 }} 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 [[##twrho|Uzupelnic twrho|]]. W algorytmie tym wyznaczać będziemy tzw. stany rozróżnialne. Algorytm działa w czasie } O(|A|n^2)$,gdzie$|A|Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest mocą alfabetu, a } nParser nie mógł rozpoznać (błąd składni): {\displaystyle -- liczbą stanów automatu wejściowego, czyli podlegajacego minimalizacji. Złożoność pamięciowa jest również } O(|A|n^2)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Natomiast w ramach ćwiczeń prezentujemy jeszcze jeden algorytm, znany jako algorytm minimalizacji Hopcrofta. Czas działania tego algorytmu wynosi } O(n n)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Niech będzie relacją zdefiniowaną przez funkcję przejść automatu w następujący sposób: }

p q w A^* (f(p,w) T f(q,w) T).

Parser nie mógł rozpoznać (nieznana funkcja „\begindefin”): {\displaystyle \begindefin Stany } p$i$qParser nie mógł rozpoznać (błąd składni): {\displaystyle są równoważne, jeśli } p qParser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle . \enddefin 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)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 } {L}[p,q]Parser nie mógł rozpoznać (błąd składni): {\displaystyle , po jednej liście dla każdej pary stanów. Funkcja } initialize({L}[p,q])Parser nie mógł rozpoznać (błąd składni): {\displaystyle inicjalizuje listę pustą, funkcja } zdejmij({L}[p,q])Parser nie mógł rozpoznać (błąd składni): {\displaystyle zdejmuje jeden z elementów, natomiast funkcja } włóż({L}[p,q],x)Parser nie mógł rozpoznać (błąd składni): {\displaystyle wkłada element } xParser nie mógł rozpoznać (błąd składni): {\displaystyle na listę } {L}[p,q]$.Funkcja$empty({L}[p,q])Parser nie mógł rozpoznać (błąd składni): {\displaystyle zwraca wartość } true$gdylistajestpusta,oraz$falseParser nie mógł rozpoznać (błąd składni): {\displaystyle w przeciwnym wypadku. Zwróćmy uwagę, że elementami każdej z list } {L}[p,q]Parser nie mógł rozpoznać (błąd składni): {\displaystyle są pary stanów } (s,t) S SParser nie mógł rozpoznać (nieznana funkcja „\newpage”): {\displaystyle . \newpage \beginalgorithm \caption{\textsc{Minimalizuj3} -- algorytm minimalizacji wykorzystujący relację } \beginalgorithmic [1] \STATE Wejście: } {A}=(S, A, f, s_0, T)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle -- automat \STATE Wyjście: } {A}'=(S', A, f', s_0', T')Parser nie mógł rozpoznać (błąd składni): {\displaystyle -- automat minimalny taki, że } L({A}')=L({A})Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle . \FOR{\textbf{each} } p TParser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle } \FOR{\textbf{each} } q S TParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{zaznaczone}} [p,q] 1Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE \textbf{initialize}(} {L}[p,q]Parser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle ) \ENDFOR \ENDFOR \FOR{} each(p,q) (T T) ((S T)

(S T))Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{zaznaczone}} [p,q] 0Parser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle ; \ENDFOR \FOR{} each (p,q) (T T) ((S T) (S T))Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE flag\textbf{false} \FOR{\textbf{each } } a AParser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle } \IF{ \textbf{zaznaczone}} [f(p,a),f(q,a)]=1Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE flag\textbf{true}; \ENDIF \ENDFOR \IF{flag=\textbf{true}} \STATE \textsc{Oznacz}} (p,q)Parser nie mógł rozpoznać (nieznana funkcja „\hfill”): {\displaystyle ;\hfill para } (f(p,a),f(q,a))Parser nie mógł rozpoznać (błąd składni): {\displaystyle była oznaczona dla pewnego } aParser nie mógł rozpoznać (nieznana funkcja „\ELSE”): {\displaystyle ; \ELSE \FOR{\textbf{each } } a AParser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle } \IF{} f(p,a) f(q,a)Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE \textbf{włóż}} ({L}[p,q],(f(p,a),f(q,a)))Parser nie mógł rozpoznać (nieznana funkcja „\ENDIF”): {\displaystyle ; \ENDIF \ENDFOR \ENDIF \ENDFOR \STATE } S' S _Parser nie mógł rozpoznać (nieznana funkcja „\hfill”): {\displaystyle ;\hfill relacja jest dopełnieniem tabeli } zaznaczoneParser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle \FOR{\textbf{each} } [s]_{ } S _Parser nie mógł rozpoznać (nieznana funkcja „\FOR”): {\displaystyle } \FOR{\textbf{each} } a AParser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE } f'([s]_{},a) [f(s,a)]_{}Parser nie mógł rozpoznać (nieznana funkcja „\ENDFOR”): {\displaystyle ; \ENDFOR \ENDFOR \STATE } s_0' [s_0]_{}Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle ; \STATE } T' [t]_{}:t TParser nie mógł rozpoznać (nieznana funkcja „\RETURN”): {\displaystyle ; \RETURN } {A}'=(S', A, f', s_0', T')Parser nie mógł rozpoznać (nieznana funkcja „\endalgorithmic”): {\displaystyle ; \endalgorithmic \endalgorithm Występujaca w algorytmie procedura \textsc{Oznacz} opisana jest poniżej. \beginalgorithm \beginalgorithmic [1] \STATE \textbf{procedure} \textsc{Oznacz}} (p,q S)Parser nie mógł rozpoznać (nieznana funkcja „\IF”): {\displaystyle \IF{\textbf{zaznaczone}} [p,q]=1Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE{ \textbf{return}} \ENDIF \STATE{\textbf{zaznaczone}} [p,q] 1Parser nie mógł rozpoznać (nieznana funkcja „\WHILE”): {\displaystyle } \WHILE{\textbf{not empty}} ({L}[p,q])Parser nie mógł rozpoznać (nieznana funkcja „\STATE”): {\displaystyle } \STATE{\textsc{Oznacz}(\textbf{zdejmij}} ({L}[p,q])Parser nie mógł rozpoznać (nieznana funkcja „\ENDWHILE”): {\displaystyle )} \ENDWHILE \STATE \textbf{end procedure} \endalgorithmic \endalgorithm 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. {{cwiczenie|[Uzupelnij]|| Zminimalizujemy automat przedstawiony na rysunku [[##ja-lekcja5-w-rys4|Uzupelnic ja-lekcja5-w-rys4|]], używając algorytmu \textsc{Minimalizuj3}. RYSUNEK ja-lekcja5-w-rys4 Proces działania algorytmu i konstrukcji tabelki przedstawiony jest na poniższej animacji }} TUTAJ ANIMACJA. Opis animacji znajduje się w pliku ja-lekcja5-w-anim1.pdf. Wygląd ekranu animacji znajduje się w pliku ja-lekcja5-w-anim1.jpg.\\ Wypełniona tabelka po zakończeniu działania algorytmu przedstawiona jest na rysunku [[##ja-lekcja5-w-rys5|Uzupelnic ja-lekcja5-w-rys5|]]. RYSUNEK ja-lekcja5-w-rys5. Z tabelki odczytujemy, że stanami równoważnymi są stany } s_1, s_5$,stany$s_2, s_8$orazstany$s_4, s_6Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Automat minimalny przedstawiony jest na rysunku [[##ja-lekcja5-w-rys6|Uzupelnic ja-lekcja5-w-rys6|]]. RYSUNEK ja-lekcja5-w-rys6.}