(Nie pokazano 34 wersji utworzonych przez 4 użytkowników) Linia 1:
Linia 1: {stre}{Streszczenie}
--- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu ---
{wsk}{Wskazówka}
{rozw}{Rozwiązanie}
{textt}{}
{thm}{Twierdzenie}[section]
{stw}[thm]{Stwierdzenie}
{lem}[thm]{Lemat}
{uwa}[thm]{Uwaga}
{exa}[thm]{Example}
{dfn}[thm]{Definicja}
{wn}[thm]{Wniosek}
{prz}[thm]{Przykład}
{zadan}[thm]{Zadanie}
{}
<quiz type="exclusive">
{}
Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które
spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności,
dziedzin i kodziedzin morfizmów.
<wrongoption>Prawda</wrongoption>
<rightoption>Fałsz</rightoption>
</quiz>
---------------------------------------------------------------------
{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}
<quiz>
Zaznacz zdania prawdziwe dotyczące podłogi i sufitu:
<option><math>n\geq 2^ {\left\lceil \log_2 n \right\rceil }</math>,</option>
<option><math>n\leq 2^ {\left\lceil \log_2 n \right\rceil }</math>,</option>
<option><math>\left\lceil \log_2 \left\lceil n/2 \right\rceil \right\rceil=\left\lceil \log_2 \left( n/2 \right) \right\rceil</math>,</option>
<option><math>\left\lfloor \log_2 \left\lceil n/2 \right\rceil \right\rfloor=\left\lfloor \log_2 \left( n/2 \right) \right\rfloor</math>.</option>
</quiz>
{algorithm}{Algorytm}
{procedure}{Procedura}
<quiz>
Dowolny niepusty podzbiór <math>S\subseteq \mathbb {N }</math> zbioru liczb naturalnych
ma w sobie liczbę największą
ma w sobie liczbę najmniejszą
ma w sobie liczbę największą oraz liczbę najmniejszą
ma w sobie liczbę najmniejszą ale nigdy nie ma największej
</quiz>
{ Algorytmy konstrukcji automatu minimalnego }
; Wprowadzenie
<quiz>
: W tym wykładzie podamy algorytmy konstrukcji automatu minimalnego
Zbiór <math>S\subseteq\mathbb{N}</math> jest taki, że jeśli <math>s\in S</math> to <math>s+1\in S</math> .
i twierdzenia dowodzące ich poprawności.<br>
Jeśli <math>9\in S </math > , to:
; Słowa kluczowe
<math>S=\mathbb{N}</math>
: automat minimalny, pochodna Brzozowskiego, algorytmy
minimalizacji.
==algorytmy konstrukcji automatu minimalnego==
<math>S =\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math>
Dla języka rozpoznawanego <math>L</math> konstrukcję automatu minimalnego można
<math>S\subseteq\mathbb{N}-\left\lbrace 0,1,2,3,4 ,5 ,6 ,7 ,8 \right\rbrace </math>
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 <math>L</math>. Prezentację poprzedzimy wprowadzeniem pewnej operacji na
słowach zwanej pochodną J.Brzozowskiego.
Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, a <math>\; u \in A^* \;</math> dowolnym
<math>S \supseteq \mathbb {N} -\left \lbrace 0,1,2,3,4,5,6,7,8 \right \rbrace </math>
słowem. '''Pochodną Brzozowskiego''' (residuum) z języka <math>L</math> względem słowa <math>u</math> nazywamy
</quiz >
język
<center><math> u^{-1}L=\{w \in A^*\;\; :\;\;\; uw \in L \}.</math></center>
Podczas obliczeń pochodnych Brzozowskiego
(residuów języka <math>L</math>) można wykorzystać poniższe równości.
Niech <math>L_1, L_2\subset A^* \;</math> będą
<quiz>
dowolnymi językami, <math>a \in A</math> dowolną literą, a <math> u,v \in A^*</math> dowolnymi słowami.
Zbiór <math>S \subseteq \mathbb{N} </math> jest taki , że jeśli <math>a,b \in S </math> ,
Prawdziwe są następujące równości:
to <math> a+b\in S </ math> oraz <math>a+b+1\not \in S </math> .
Jeśli <math>0,2 \in S</math> , to :
<center><math>\aligned\nonumber u^{-1}(L_1 \cup L_2) & = & u^{-1}L_1 \cup u^{-1}L_2, \\
<math>S =\mathbb {N }</math>
\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</math></center>
{{cwiczenie|[Uzupelnij]||
zbiór <math>S</math> zawiera wszystkie liczby naturalne, które są parzyste
Obliczmy wszystkie pochodne dla języka <math>L=a^+b^+</math>. Okazuje się, że są tylko
zbiór <math>S </math> jest zawarty w zbiorze liczb naturalnych , które są parzyste
cztery różne pochodne liczone względem <math>a</math>, <math>b</math>, <math>ab</math> i słowa pustego <math>1</math>. Mianowicie:<br>
<math> a^{-1}L=a^*b^+ </math>,<br>
<math> b^{-1}L= \emptyset </math>,<br>
<math>ab^{-1} L=b^*</math>,<br>
<math>1^{-1}L=L</math>.<br>
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ń: <br>
<math>\forall n \in \mathbb{N} (a^n)^{-1}L=a^*b^+ </math>,<br>
<math>\forall n \in \mathbb{N} (b^n)^{-1}L= \emptyset </math>,<br>
<math>\forall n \in \mathbb{N}(ab^n)^{-1} L=b^*</math>.
}}
Zauważmy również, nawiązując raz jeszcze do rezulatów
zbiór <math>S </math> jest zbiorem wszystkich liczb naturalnych, które są parzyste
przedstawionych w poprzednim wykładzie, że prawdziwa jest
</quiz >
następująca równoważność wiążąca wprowadzone pojęcie pochodnej
Brzozowskiego z prawą kongruencją syntaktyczną:
<center><math>u \;P{^r}_L\; v \Longleftrightarrow u^{-1}L=v^{-1}L.</math></center>
Rozpisując z definicji lewą stronę tej równoważności, otrzymujemy,
iż dla dowolnego słowa <math>z \in A^*</math> słowo <math>uz \in L</math> wtedy i tylko
wtedy, gdy <math>vz \in L</math>. A to równoważnie oznacza (znów z definicji),
że <math>u^{-1}L=v^{-1}L.</math>
Z uzasadnionej równoważności oraz twierdzenia 3.4 o prawej kongruencji syntaktycznej z
<quiz>
poprzedniego wykładu wnioskujemy równoważność rozpoznawalności języka <math>L</math>
Ostatnią cyfrą liczby <math>3^{3^n} </math> jest:
i skończonej ilości różnych pochodnych Brzozowskiego tego języka.
Pierwszy z przedstawianych algorytmów będzie konstruował automat
zawsze <math>3 </math>
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 <math>L</math>, ustanawiamy
stan początkowy automatu jako <math>L</math>, wpisujemy go na listę
<math>\mathcal{L}</math> i obliczamy <math>a^{-1}L</math> dla każdej litery <math>a \in A</math>.
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:
<center><math>f(X, a)=a^{-1}X,</math></center> gdzie <math>X</math> jest pewnym językiem z listy <math>\mathcal{L}</math>.
Obliczone języki określają stany automatu minimalnego.
---- dla dociekliwych - start ----
zawsze <math>3</math> lub <math>7</math>
Obliczone języki określające stany automatu minimalnego to
zawsze <math>7 </math>
elementy monoidu syntaktycznego języka <math>L</math>.
---- dla dociekliwych - end ----
jakakolwiek z cyfr <math>0,1,2,3,4,5,6,7,8,9</math>
</quiz>
Automatem minimalnym dla automatu <math>\mathcal{A}=(S, A, f, s_0, T)</math>
będzie zatem automat
<center><math>\mathcal{A}_L=(S_L, A, f_L, s_0^L, T_L),</math></center>
gdzie:
* <math>S_L=\{u^{-1}L:\ u \in A^*\}</math>,
<quiz>
Jeśli <math>Z \subseteq \mathbb {N}</math> jest jakimś zbiorem liczb naturalnych,
który wraz z każdym początkowym fragmentem zbioru <math>\mathbb {N}</math>
postaci <math>\left\lbrace 0,\ldots,k -1 \right \rbrace</math> zawiera również kolejną liczbę <math>k </math>, to wtedy
* <math>s_0^L = L </math>,
zbiór <math>Z </math> zawiera wszystkie liczby naturalne poza skończonym podzbiorem
* <math>T_L = \{u^{-1}L:\ u \in L\}</math>,
zbiór <math>Z </math> zawiera wszystkie liczby naturalne
* <math>f_L(u^{-1}L,a) = a^{-1}(u^{-1}L)=(ua)^{-1}L</math>.
zbiór <math>Z </math> zawiera nieskończenie wiele liczb naturalnych
Jeśli zdefiniujmy odwzorowanie <math>\nu: S \rightarrow S_L</math>, kładąc:
zbiór <math>Z </math> jest pusty
<center><math>\nu(s)=u^{-1}L, \mbox{ gdzie } s=f(s_0,u),</math></center> to można dowieść,
</quiz >
że <math>\nu</math> jest dobrze określone, jest epimorfizmem oraz <math>\nu(s_0) =
s_0^L</math> - porównaj twierdzenie 3.1 z wykładu 4. Prawdą jest też, iż
<math>s \in T</math> wtedy i tylko wtedy, gdy <math>\nu(s) \in T_L</math> oraz że
następujący diagram komutuje:
<center><math>\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 </math></center>
Formalny zapis algorytmu przedstawiony jest poniżej.
<quiz>
Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić?
{{Minimalizuj1} - algorytm minimalizacji
klasa na pewno się nie pogodzi
wykorzystujący pochodne Brzozowskiego}
[1]
Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że
<math>L=L(\mathcal{A})</math>
Wyjście: automat minimalny <math>\mathcal{A}'=(S_L, A, f_L, s_L,
klasa się pogodzi , jeżeli każdy pójdzie za radą pierwszego ucznia
T_L)</math> dla <math>\mathcal{A}S_L \leftarrow \{L\}</math>;
'''włóż'''<math>(\mathcal{L},L)</math>;
jeżeli w klasie byłaby już jedna osoba , to reszta klasy miałaby szansę się pogodzić
{<math>\mathcal{L} \not =</math>}
jeżeli w klasie byłyby już co najmniej dwie osoby,
przy czym osoby w klasie byłyby ze sobą pogodzone,
to reszta klasy miałaby szansę się pogodzić
</quiz >
<math>M \leftarrow </math> '''zdejmij'''<math>(\mathcal{L})</math>;
<quiz >
{'''each''' <math>a \in A</math>}
Jeśli <math>S \subseteq \mathbb {N}</math> , to :
<math>N \leftarrow a^{-1}M</math>;
zbiór <math>S</math> ma element największy
{<math>N \cap S_L = </math> }
zbiór <math>S</math> ma element najmniejszy
<math>S_L \leftarrow S_L \cup \{N\}</math>;
zbiór <math>S</math> ma element największy , o ile <math>S</math> jest niepusty
'''włóż'''<math>(\mathcal{L},N)</math>;
zbiór <math>S</math> ma element najmniejszy , o ile <math>S</math> jest niepusty
</quiz >
{'''each''' <math>M \in S_L</math>}
{'''each''' <math>a \in A</math>}
<math>f_L(M,a) \leftarrow a^{-1}M</math>;
<math>s_L \leftarrow L</math>;
<math>T_L \leftarrow \{u^{-1}L:\ u \in L\}</math>;
<math>\mathcal{A}'</math>;
Funkcja '''zdejmij'''<math>(\mathcal{L})</math>, występująca w linii 6.,
zdejmuje z kolejki <math>\mathcal{L}</math> pierwszy element i zwraca go jako
swoją wartość. Procedura '''włóż'''<math>(\mathcal{L},L)</math>, występująca
w liniach 4. oraz 11., wstawia na koniec kolejki <math>\mathcal{L}</math>
element <math>L</math>.
{{cwiczenie|[Uzupelnij]||
Dla języka <math>L=a^+b^+</math> z przykładu 1.1 w wyniku działania powyższego algorytmu
otrzymamy czterostanowy automat
<math>\mathcal{A}_L=(S_L,A, f, L, T),</math> gdzie<br>
<math>S_L= \{L, a^*b^+ ,\emptyset, b^*\}</math>,<br>
a funkcja
przejść zadana jest grafem: <br>
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
<math>L </math>.
---- dla dociekliwych - start -----
Algorytm oblicza również monoid syntaktyczny języka <math>L </math>.
---- dla dociekliwych - end -----
Analogicznie do konstrukcji relacji <math>\rho _{i} </math>, przedstawionej
w wykładzie 4, możemy określić ciąg odpowiednich relacji na
zbiorze stanów dowolnego automatu rozpoznającego język <math>L </math>.
Relacje te służą do efektywnego określenia automatu minimalnego,
równoważnego zadanemu.
Niech <math>\mathcal{A} </math></center><nowiki>=</nowiki> (S,A,f,s_0,T)<math> będzie dowolnym automatem i
niech </math>L<nowiki>=</nowiki>L({A}) <math>.
Przez </math> _{{A}} S S <math> oznaczmy relację
równoważności
zawierającą dwie klasy równoważności </math>T<math> i </math>S T<math>. Przez </math>{}_i<math> dla </math>i { N} <math>
oznaczmy zstępujący ciąg relacji określony następująco:
</math>{}_1 <nowiki>=</nowiki> _{{A}} <math>, a dla </math> i <nowiki>=</nowiki> 2,... <math> przyjmijmy
</math>{}_i <nowiki>=</nowiki> (s,t) S S : a A 1 f(s,a) {}_{i-1} f(t,a) . <math>
{\par\raggedright Wtedy </math> {}_i <math> jest największą prawą kongruencją automatową zawartą w relacji </math>{}_1 <nowiki>=</nowiki> _{{A}} <math> i automat minimalny ma postać\par}
</math></center>{A}_{L}<nowiki>=</nowiki>( S/_{ { }_{i}},A,f^{*},[s_{0}],T/_{ { }_{i}}) .<center><math>
\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 </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math>, konstruuje
efektywnie automat minimalny dla </math>{A}<math>, obliczając ciąg
relacji </math>{}_i<math>. Proces konstrukcji przebiega w sposób
iteracyjny. Zaczynamy od zdefiniowania relacji
</math>_{{A}}<math>, 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
</math></center> s, t Ss _{{A}} t (s T t T) (s S T t S T).<center><math>
Definiujemy pierwszą z relacji </math>{}<math>, czyli relację
</math>{}_1<math> jako równą </math>_{{A}}<math>, a
następnie, dla każdej obliczonej już relacji
</math>{}_{i-1}<math>, obliczamy relację </math>{}_i<math> w
następujący sposób:
</math></center>s_1 {}_i
s_2 (s_1 {}_{i-1} s_2) (
a Af(s_1, a) {}_{i-1} f(s_2,a)).<center><math> Nowo obliczona
relacja </math>{}_i<math> albo podzieli jedną lub kilka klas
abstrakcji relacji </math>{}_{i-1}<math>, albo będzie identyczna z
relacją </math>{}_{i-1}<math>. Jeśli zajdzie ta druga sytuacja, to
znaczy, że dla każdego </math>j>i<math> w oczywisty sposób spełniona jest
równość </math>{_j}<nowiki>=</nowiki>{}_i<math>, czyli ciąg relacji
ustabilizuje się. W tym momencie algorytm kończy swoje działanie i
klasy abstrakcji relacji </math>{}_i<math> 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: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat taki, że
</math>L<nowiki>=</nowiki>L({A})<math>.
\STATE Wyjście: automat minimalny </math>{A}'<nowiki>=</nowiki>(S',A',f', s_0',
T')<math> dla </math>{A}<math>.
\STATE </math>{}_1_{{A}}<math>;
\STATE </math>i 1<math>;
\REPEAT
\STATE oblicz </math>{}_i<math>: </math>s_1
{}_i s_2 (s_1 {}_{i-1}
s_2) ( a Af(s_1, a) {}_{i-1}
f(s_2,a))<math>;
\STATE </math>i i+1<math>;
\STATE \textbf{empty}</math>({}_i)<math>
\FOR{\textbf{each} </math>(s_1,s_2) S S<math>}
\STATE flag\textbf{true};
\FOR{\textbf{each} </math>a A<math>}
\IF{\textbf{not} </math>f(s_1, a) {}_{i-1} f(s_2,a)<math>}
\STATE flag\textbf{false};
\ENDIF
\ENDFOR
\IF{flag=\textbf{true} \textbf{and} </math>s_1 {}_{i-1} s_2<math>}
\STATE </math>{}_{i} {}_{i}
(s_1,s_2)<math>;
\ENDIF
\ENDFOR
\UNTIL{</math>{}_i <nowiki>=</nowiki> {}_{i-1}<math>}
\STATE </math>S' S {}_i<math>;
\FOR{\textbf{each} </math>[s]_{{}_i} S
{}_i<math>}
\FOR{\textbf{each} </math>a A<math>}
\STATE </math>f'([s]_{{}_i},a)
[f(s,a)]_{{}_i}<math>;
\ENDFOR
\ENDFOR
\STATE </math>s_0' [s_0]_{{}_i}<math>;
\STATE </math>T' [t]_{{}_i}:t T<math>;
\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
\endalgorithmic
\endalgorithm
{{cwiczenie|[Uzupelnij]||
Zminimalizujemy automat </math>{A}<nowiki>=</nowiki>(S,A,f,s_0,T)<math>, dla którego\\
</math>S<nowiki>=</nowiki> s_{0},s_{1},s_{2},s_{3},s_{4},s_5 , A<nowiki>=</nowiki>a,b,
T<nowiki>=</nowiki>s_1, s_{2},s_{4} <math>,
a funkcja przejść określona jest przy pomocy grafu.\\
RYSUNEK ja-lekcja5-w-rys2\\
Konstruujemy ciąg
relacji </math>{}_i<math>.
Na początku </math>{}_1<math> dzieli </math>S<math> na dwie klasy
abstrakcji; pierwsza zawiera stany końcowe, a druga -- wszystkie
pozostałe, czyli uzyskujemy dwa zbiory </math>s_1,s_2,s_4<math> oraz
</math>s_0, s_3, s_5<math>.Obliczmy </math>{}_2<math> (pierwszy przebieg pętli w liniach 5.-20. algorytmu). Aby dwa elementy
(stany) </math>s<math> i </math>t<math> były ze sobą w relacji </math>{}_2<math> muszą
być ze sobą w relacji </math>{}_1<math> oraz musi zachodzić
</math></center> a A f(s, a) {}_1 f(t,a).<center><math>
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
</math>{}_{i+1}<math> znajdą się elementy z różnych klas
abstrakcji relacji </math>{}_i<math>.
Rozważmy najpierw zbiór </math>s_1, s_2, s_4<math>. Oczywiście każde dwa
stany z tego zbioru są ze sobą w relacji </math>{}_1<math>.
Zauważmy, że </math>f(s_2, a)<nowiki>=</nowiki>f(s_4,a)<nowiki>=</nowiki>s_2<math>, </math>f(s_2,b)<nowiki>=</nowiki>f(s_4,b)<nowiki>=</nowiki>s_4<math>, więc
</math>s_2 {}_2 s_4<math> (bo </math>s_2 {}_1 s_2<math> oraz </math>s_4 {}_1 s_4<math>).
Ponieważ </math>f(s_1,b)<nowiki>=</nowiki>s_5<math> i </math>f(s_2,b)<nowiki>=</nowiki>s_4<math>, a wiemy, że </math>s_5<math> nie jest
w relacji </math>{}_1<math> z </math>s_4<math>, zatem stany </math>s_1<math> i </math>s_2<math>
nie mogą być ze sobą w relacji </math>{}_2<math>, a to oznacza, że
także stany </math>s_1<math> i </math>s_4<math> nie mogą być ze sobą w relacji
</math>{}_2<math>.
W analogiczny sposób można sprawdzić, że relacja </math>{}_2<math> nie
podzieli zbioru </math>s_0, s_3, s_5<math>. Ostatecznie, po pierwszym
wykonaniu pętli algorytmu minimalizacji obliczyliśmy relację
</math>{}_2<math>, która dzieli </math>S<math> na następujące podzbiory:
</math></center>s_1, s_2, s_4, s_0, s_3, s_5.<center><math>
W kolejnym kroku obliczamy </math>{}_3<math>. Zbiór </math>s_1<math>
oczywiście nie może być już podzielony na mniejsze podzbiory.
Łatwo zauważyć, że </math>{}_3<math> nie podzieli także zbioru </math>s_2,
s_4<math>.
Rozważmy teraz zbiór </math>s_0, s_3, s_5<math>. Mamy </math>f(s_3, a)<nowiki>=</nowiki>f(s_5, a)<math> oraz
</math>f(s_3, b)<nowiki>=</nowiki>s_3<math>, </math>f(s_5, b)<nowiki>=</nowiki>s_5<math> i wiadomo, że </math>s_3 {}_2
s_5<math>, zatem </math>s_3<math> i </math>s_5<math> będą ze sobą w relacji
</math>{}_3<math>.
Ponieważ </math>f(s_0, a)<nowiki>=</nowiki>s_2<math> i </math>f(s_3, a)<nowiki>=</nowiki>s_1<math>, ale </math>s_2<math> i </math>s_1<math> nie są
ze sobą w relacji </math>{}_2<math>, zatem nie mogą być także ze
sobą w relacji </math>{}_3<math>. Relacja </math>{}_3<math>
dzieli więc zbiór </math>s_0, s_3, s_5<math> na zbiory </math>s_0<math> oraz
</math>s_3, s_5<math>.
Podział zbioru </math>S<math> przez relację </math>{}_3<math> wygląda więc
następująco: </math></center>s_0, s_1, s_2, s_4, s_3, s_5.<center><math>
Relacja </math>{}_4<math> nie podzieli już ani zbioru </math>s_2,
s_4<math>, ani zbioru </math>s_3, s_5<math>, więc uzyskujemy równość
</math>{_4}<nowiki>=</nowiki>{}_3<math> i ponieważ ciąg relacji się
ustabilizował, algorytm kończy działanie.
Podsumowując, mamy:
; </math>{} _{1}<math>
: </math>s_1, s_{2},s_{4}, s_{0},s_{3},s_5, <math>
; </math>{} _{2}<math>
: </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5,<math>
; </math>{} _{3}<math>
: </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5.{} _{3}<nowiki>=</nowiki>{} _{4}<math> i równoważny minimalny automat </math>{A}_L<nowiki>=</nowiki>(S,f^*,s_0,T)<math> ma </math>4<math> stany. \\
</math>q_0<nowiki>=</nowiki>s_{0}, q_1<nowiki>=</nowiki>s_{1}, q_2 <nowiki>=</nowiki> s_2,s_{4}, q_3
<nowiki>=</nowiki>s_{3},s_5<math>, </math>T<nowiki>=</nowiki>q_1 ,q_2<math>.
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 </math>O(|A|n^2)<math>, gdzie </math>|A|<math> jest mocą
alfabetu, a </math>n<math> -- liczbą stanów automatu wejściowego, czyli
podlegajacego minimalizacji. Złożoność pamięciowa jest również
</math>O(|A|n^2)<math>. 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ą -
</math>O(|A|n)<math>. Natomiast w ramach ćwiczeń prezentujemy jeszcze jeden
algorytm, znany jako algorytm minimalizacji Hopcrofta. Czas
działania tego algorytmu wynosi </math>O(n n)<math>.
Niech będzie relacją zdefiniowaną przez funkcję przejść automatu
w następujący sposób:
</math></center>p q w A^* (f(p,w) T
f(q,w) T).<center><math>
\begindefin
Stany </math>p<math> i </math>q<math> są równoważne, jeśli </math>p q<math>.
\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 </math>(p,q)<math>, 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 </math>{L}[p,q]<math>,
po jednej liście dla każdej pary stanów. Funkcja
</math>'''initialize'''({L}[p,q])<math> inicjalizuje listę pustą,
funkcja </math>'''zdejmij'''({L}[p,q])<math> zdejmuje jeden z
elementów, natomiast funkcja
</math>'''włóż'''({L}[p,q],x)<math> wkłada element </math>x<math> na listę
</math>{L}[p,q]<math>. Funkcja </math>'''empty'''({L}[p,q])<math>
zwraca wartość </math>'''true'''<math> gdy lista jest pusta, oraz
</math>'''false'''<math> w przeciwnym wypadku. Zwróćmy uwagę, że elementami
każdej z list </math>{L}[p,q]<math> są pary stanów </math>(s,t) S S<math>.
\newpage
\beginalgorithm
\caption{\textsc{Minimalizuj3} -- algorytm minimalizacji
wykorzystujący relację }
\beginalgorithmic [1]
\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat
\STATE Wyjście: </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math> -- automat
minimalny taki, że </math>L({A}')<nowiki>=</nowiki>L({A})<math>.
\FOR{\textbf{each} </math>p T<math>}
\FOR{\textbf{each} </math>q S T<math>}
\STATE \textbf{zaznaczone}</math>[p,q] 1<math>;
\STATE \textbf{initialize}(</math>{L}[p,q]<math>)
\ENDFOR
\ENDFOR
\FOR{</math>'''each'''(p,q) (T T) ((S T)
(S T))<math>}
\STATE \textbf{zaznaczone}</math>[p,q] 0<math>;
\ENDFOR
\FOR{</math>'''each ''' (p,q) (T T) ((S T)
(S T))<math>}
\STATE flag\textbf{false}
\FOR{\textbf{each } </math>a A<math>}
\IF{ \textbf{zaznaczone}</math>[f(p,a),f(q,a)]<nowiki>=</nowiki>1<math>}
\STATE flag\textbf{true};
\ENDIF
\ENDFOR
\IF{flag=\textbf{true}}
\STATE \textsc{Oznacz}</math>(p,q)<math>;\hfill para
</math>(f(p,a),f(q,a))<math> była oznaczona dla pewnego </math>a<math>;
\ELSE
\FOR{\textbf{each } </math>a A<math>}
\IF{</math>f(p,a) f(q,a)<math>}
\STATE \textbf{włóż}</math>({L}[p,q],(f(p,a),f(q,a)))<math>;
\ENDIF
\ENDFOR
\ENDIF
\ENDFOR
\STATE </math>S' S _<math>;\hfill
relacja jest dopełnieniem tabeli </math>'''zaznaczone'''<math>
\FOR{\textbf{each} </math>[s]_{ } S _<math>}
\FOR{\textbf{each} </math>a A<math>}
\STATE </math>f'([s]_{},a) [f(s,a)]_{}<math>;
\ENDFOR
\ENDFOR
\STATE </math>s_0' [s_0]_{}<math>;
\STATE </math>T' [t]_{}:t T<math>;
\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
\endalgorithmic
\endalgorithm
Występujaca w algorytmie procedura \textsc{Oznacz} opisana jest poniżej.
\beginalgorithm
\beginalgorithmic [1]
\STATE \textbf{procedure} \textsc{Oznacz}</math>(p,q S)<math>
\IF{\textbf{zaznaczone}</math>[p,q]<nowiki>=</nowiki>1<math>}
\STATE{ \textbf{return}}
\ENDIF
\STATE{\textbf{zaznaczone}</math>[p,q] 1<math>}
\WHILE{\textbf{not empty}</math>({L}[p,q])<math>}
\STATE{\textsc{Oznacz}(\textbf{zdejmij}</math>({L}[p,q])<math>)}
\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 </math>s_1, s_5<math>,
stany </math>s_2, s_8<math> oraz stany </math>s_4, s_6<math>. Automat minimalny
przedstawiony jest na rysunku [[##ja-lekcja5-w-rys6|Uzupelnic ja-lekcja5-w-rys6|]].
RYSUNEK ja-lekcja5-w-rys6.</math>
--- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu ---
Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które
spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności,
dziedzin i kodziedzin morfizmów.
Źle
Dobrze
n ≥ 2 ⌈ log 2 n ⌉
n ≤ 2 ⌈ log 2 n ⌉
⌈ log 2 ⌈ n / 2 ⌉ ⌉ = ⌈ log 2 ( n / 2 ) ⌉
⌊ log 2 ⌈ n / 2 ⌉ ⌋ = ⌊ log 2 ( n / 2 ) ⌋
S ⊆ ℕ
ma w sobie liczbę najmniejszą
ma w sobie liczbę największą oraz liczbę najmniejszą
ma w sobie liczbę najmniejszą ale nigdy nie ma największej
S ⊆ ℕ s ∈ S s + 1 ∈ S 9 ∈ S
S = ℕ
S = ℕ − { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }
S ⊆ ℕ − { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }
S ⊇ ℕ − { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 }
S ⊆ ℕ a , b ∈ S a + b ∈ S a + b + 1 ∉ S 0 , 2 ∈ S
S = ℕ
zbiór S
zbiór S
zbiór S
3 3 n
zawsze 3
zawsze 3 7
zawsze 7
jakakolwiek z cyfr 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
Z ⊆ ℕ ℕ { 0 , … , k − 1 } k
zbiór Z
zbiór Z
zbiór Z
zbiór Z
klasa na pewno się nie pogodzi
klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia
jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić
jeżeli w klasie byłyby już co najmniej dwie osoby,
przy czym osoby w klasie byłyby ze sobą pogodzone,
to reszta klasy miałaby szansę się pogodzić
S ⊆ ℕ
zbiór S
zbiór S
zbiór S S
zbiór S S
