|
|
| (Nie pokazano 71 wersji utworzonych przez 2 użytkowników) |
| Linia 1: |
Linia 1: |
| W tym wykładzie podamy algorytmy konstrukcji automatu minimalnego
| | <quiz type="exclusive"> |
| i twierdzenia dowodzące ich poprawności.<br>
| |
|
| |
|
| ==Algorytmy konstrukcji automatu minimalnego==
| |
|
| |
|
| Dla języka rozpoznawanego <math>L</math> 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 <math>L</math>. Prezentację poprzedzimy wprowadzeniem pewnej operacji na słowach zwanej pochodną J.Brzozowskiego.
| | </quiz> |
|
| |
|
| {{definicja|1.1.||
| |
|
| |
|
| Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, a <math>\; u \in A^* \;</math> dowolnym słowem. '''Pochodną Brzozowskiego''' (residuum) z języka <math>L</math> względem słowa <math>u</math> nazywamy 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.
| | 1111111111111111111111111111111111111111111 |
|
| |
|
| Niech <math>L_1, L_2\subset A^* \;</math> będą dowolnymi językami, <math>a \in A</math> dowolną literą, a <math> u,v \in A^*</math> dowolnymi słowami. Prawdziwe są następujące równości:
| |
|
| |
|
| <center><math>\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}</math></center>
| |
|
| |
|
| {{przyklad|1.1.||
| | 1111111111111111111111111111111111111111111 |
|
| |
|
| Obliczmy wszystkie pochodne dla języka <math>L=a^+b^+</math>. Okazuje się, że są tylko 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 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ą:
| |
|
| |
|
| <center><math>u \;P{^r}_L\; v \Longleftrightarrow u^{-1}L=v^{-1}L.</math></center>
| | 22222222222222222222222222222222222222222 |
|
| |
|
| 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>
| | ==Ciągi w przestrzeniach metrycznych. Test== |
|
| |
|
| 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 <math>L</math> 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 <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
| | 3333333333333333333333333333333333333333333333333333333333333 |
| 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>.
| | ==Norma. Iloczyn skalarny. Test== |
|
| |
|
| Obliczone języki określają stany automatu minimalnego.
| |
|
| |
|
| {{uwaga|[Dla zainteresowanych]||
| | 444444444444444444444444444444444444444444444444444444444444444 |
|
| |
|
| Obliczone języki określające stany automatu minimalnego to
| | ==Ciągi i szeregi funkcyjne. Szereg Taylora. Test== |
| elementy monoidu syntaktycznego języka <math>L</math>.
| |
| }}
| |
| 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> | | <quiz> |
| gdzie:
| | Dany jest ciąg funkcyjny <math>\{f_n\}</math> gdzie |
| | <math> |
| | f_n(x)= |
| | \left\{ |
| | \begin{array} {lll} |
| | 1 & \text{dla} & x\in[n,n+1]\\ |
| | 0 & \text{dla} & x\in \mathbb{R}\setminus[n,n+1] |
| | \end{array} |
| | \right</math> |
| | dla <math>n\in\mathbb{N}</math> |
| | Ciąg ten jest |
| | <rightoption>zbieżny punktowo do <math>f(x)\equiv 0</math></rightoption> |
| | <wrongoption>zbieżny jednostajnie do <math>f(x)\equiv 0</math></wrongoption> |
| | <wrongoption>zbieżny punktowo do funkcji <math>f(x)= |
| | \left\{ |
| | \begin{array} {lll} |
| | 1 & \text{dla} & x\geq 1\\ |
| | 0 & \text{dla} & x<0 |
| | \end{array} |
| | \right</math></wrongoption> |
| | </quiz> |
|
| |
|
| * <math>S_L=\{u^{-1}L:\ u \in A^*\}</math>,
| | tak, nie, nie |
|
| |
|
| * <math>s_0^L = L </math>,
| | <quiz> |
| | Dany jest ciąg funkcyjny <math>\{f_n\}</math> gdzie |
|
| |
|
| * <math>T_L = \{u^{-1}L:\ u \in L\}</math>,
| | <center><math>f_n(x)= |
| | \left\{ |
| | \begin{array} {lll} |
| | \frac{1-n^{-x}}{1+n^{-x}} & \text{dla} & x>0\\ |
| | \\ |
| | \frac{2-n^{x}}{2+n^{x}} & \text{dla} & x<0\\ |
| | \\ |
| | 0 & \text{dla} & x=0\\ |
| | \end{array} |
| | \right. |
| | \quad</math> dla <math>\ n=1,2,\ldots |
| | </math></center> |
|
| |
|
| * <math>f_L(u^{-1}L,a) = a^{-1}(u^{-1}L)=(ua)^{-1}L</math>.
| | Ten ciąg funkcyjny jest |
| | <wrongoption>zbieżny jednostajnie</wrongoption> |
| | <rightoption>zbieżny punktowo ale nie jednostajnie</rightoption> |
| | <wrongoption>rozbieżny</wrongoption> |
| | </quiz> |
|
| |
|
| Jeśli zdefiniujmy odwzorowanie <math>\nu: S \rightarrow S_L</math>, kładąc:
| | nie, tak, nie |
| <center><math>\nu(s)=u^{-1}L, \mbox{ gdzie } s=f(s_0,u),</math></center>
| |
|
| |
|
| to można dowieść, ż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:
| | <quiz> |
| | Dany jest ciąg funkcyjny <math>f_n(x)=\sqrt[n]{x}</math> dla <math>x\ge 0</math> Ten ciąg |
| | <wrongoption>jest zbieżny punktowo i jego granica jest ciągła</wrongoption> |
| | <wrongoption>jest zbieżny jednostajnie i jego granica jest ciągła</wrongoption> |
| | <rightoption>jest zbieżny punktowo i jego granica nie jest ciągła</rightoption> |
| | </quiz> |
|
| |
|
| <center><math>\beginCD
| | nie, nie, tak |
| 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> |
| {{algorytm|Minimalizuj1 - algorytm minimalizacji wykorzystujący pochodne Brzozowskiego|algorytm minimalizacji wykorzystujący pochodne Brzozowskiego|
| | Dany jest szereg <math>\sum_{n=1}^{\infty}\frac{\sin nx}{2^n(x^2+1)}, \ x\in \mathbb{R}</math> Ten szereg jest |
| 1 Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>L=L(\mathcal{A})</math>
| | <wrongoption>zbieżny jednostajnie do funkcji <math>f(x)\equiv 0</math></wrongoption> |
| 2 Wyjście: automat minimalny <math>\mathcal{A}'=(S_L, A, f_L, s_L,
| | <rightoption>zbieżny jednostajnie do funkcji <math>f</math> takiej, że <math>0<f(x)<3</math></rightoption> |
| T_L)</math> dla <math>\mathcal{A}S_L \leftarrow \{L\}</math>;
| | <wrongoption>zbieżny jednostajnie do funkcji <math>f(x)=\frac{1}{2(x^2+1)}</math></wrongoption> |
| 3 <math>S_L \leftarrow \{L\}</math>
| | </quiz> |
| 4 '''włóż'''<math>(\mathcal{L},L)</math>;
| |
| 5 '''while''' <math>\mathcal {L}\ne \emptyset</math> '''do'''
| |
| 6 <math>M \leftarrow</math> '''zdejmij'''(<math>\mathcal {L}</math>);
| |
| 7 '''for''' '''each''' <math>a \in A</math> '''do'''
| |
| 8 <math>N \leftarrow a^{-1}M</math>;
| |
| 9 '''if''' <math>N \cap S_L = \emptyset</math> '''then'''
| |
| 10 <math>S_L \leftarrow S_L \cup \{N\}</math>;
| |
| 11 '''włóż'''<math>(\mathcal{L},N)</math>;
| |
| 12 '''end''' '''if'''
| |
| 13 '''end''' '''for'''
| |
| 14 '''end''' ''' while'''
| |
| 15 '''for''' '''each''' <math>M \in S_L</math> '''do'''
| |
| 16 '''for''' '''each''' <math>a \in A</math> '''do'''
| |
| 17 <math>f_L(M,a) \leftarrow a^{-1}M</math>;
| |
| 18 '''end''' '''for'''
| |
| 19 '''end''' '''for'''
| |
| 20 <math>s_L \leftarrow L</math>;
| |
| 21 <math>T_L \leftarrow \{u^{-1}L:\ u \in L\}</math>;
| |
| 22 '''return''' <math>\mathcal{A}'</math>;
| |
| }}
| |
|
| |
|
| | nie, tak, nie |
|
| |
|
| 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>. | | <quiz> |
| | Funkcja <math> |
| | f(x):=\sum_{n=1}^{\infty}\frac{\sqrt[n]{x}}{n(n+1)(x^2+1)}</math> |
| | Granica <math>\lim_{x\to 3}f(x)</math> wynosi |
| | <rightoption><math>\frac{1}{10}</math></rightoption> |
| | <wrongoption><math>\sqrt{3}</math></wrongoption> |
| | <wrongoption><math>0</math></wrongoption> |
| | </quiz> |
|
| |
|
| {{przyklad|1.2.||
| | tak, nie, nie |
|
| |
|
| Dla języka <math>L=a^+b^+</math> z przykładu 1.1 w wyniku działania powyższego algorytmu
| | <quiz> |
| otrzymamy czterostanowy automat
| | Szereg <math>\sum_{n=1}^{\infty}\frac{1}{n(x^4+4)}</math> jest |
| <math>\mathcal{A}_L=(S_L,A, f, L, T),</math> gdzie<br> | | <wrongoption>zbieżny punktowo</wrongoption> |
| <math>S_L= \{L, a^*b^+ ,\emptyset, b^*\}</math>,<br> | | <wrongoption>zbieżny jednostajnie </wrongoption> |
| a funkcja
| | <rightoption>rozbieżny</rightoption> |
| przejść zadana jest grafem: <br>
| | </quiz> |
|
| |
|
| RYSUNEK ja-lekcja5-w-rys1
| | nie, nie, tak |
|
| |
|
| }} | | <quiz> |
| | Czwarty z kolei wyraz rozwinięcia w szereg Maclaurina funkcji <math>f(x)=\cos 2x</math> to |
| | <wrongoption><math>-\frac{2^6}{6!}</math></wrongoption> |
| | |
| | <wrongoption><math>\frac{2^6}{6!}x^6</math></wrongoption> |
| | |
| | <rightoption><math>\frac{-4}{45}x^6</math></rightoption> |
| | </quiz> |
|
| |
|
| 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>.
| | nie, nie, tak |
|
| |
|
| {{uwaga|[Dla zainteresowanych]|| | | <quiz> |
| | Szósty z kolei wyraz rozwinięcia w szereg Taylora funkcji <math>f(x)=\frac{1}{2+x}</math> o środku w <math>x_0=0</math> wynosi |
| | <wrongoption><math>\frac{-1}{64}x^6</math></wrongoption> |
| | |
| | <rightoption><math>\frac{-1}{64}x^5</math></rightoption> |
| | |
| | <wrongoption><math>\frac{1}{2}x^6</math></wrongoption> |
| | </quiz> |
|
| |
|
| Algorytm oblicza również monoid syntaktyczny języka <math>L </math>.
| | nie, tak, nie |
|
| |
|
| }} | | <quiz> |
| | Sumujemy cztery kolejne wyrazy rozwinięcia w szereg Taylora funkcji <math>\sqrt{x}</math> ośrodku w <math>x_0=1</math> Współczynnik przy <math>x</math> wynosi |
| | <rightoption><math>\frac{15}{16}</math></rightoption> |
| | |
| | <wrongoption><math>\frac{5}{16}</math></wrongoption> |
| | |
| | <wrongoption><math>\frac{1}{16}</math></wrongoption> |
| | </quiz> |
|
| |
|
| 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.
| | tak, nie, nie |
|
| |
|
| twierdzenie|1.1.||
| | 5555555555555555555555555555555555555555555555555555 |
|
| |
|
| Niech <math>\mathcal{A}= (S,A,f,s_0,T)</math> będzie dowolnym automatem i niech <math>L = L(\mathcal{A})</math>. Przez <math>\approx _\mathcal{A} \subset S \times S</math> oznaczmy relację równoważności zawierającą dwie klasy równoważności <math>T</math> i <math>S\setminus T</math>. Przez <math>\overline \rho_i</math> dla <math>i\in \Bbb N</math>
| | ==Szereg potęgowy. Trygonometryczny szereg Fouriera. Test== |
| oznaczmy zstępujący ciąg relacji określony następująco:
| |
|
| |
|
| <math>\overline \rho _1 = \approx _\mathcal{A} </math>, a dla <math> i = 2,... </math> przyjmijmy
| |
|
| |
|
| <math>\overline \rho _i = \{ (s,t) \in \; S \times S \; : \;\; \forall a \in A \cup \{1\} \; \; f(s,a) \overline{\rho}_{i-1} f(t,a) \;\}. \;</math>.
| | 101010101010101010101010101010101010101010101010101010101010 |
|
| |
|
| Wtedy <math>\bigcap \overline \rho_i</math> jest największą prawą kongruencją automatową zawartą w relacji <math>\overline \rho_1 = \approx _ \mathcal{A} </math> i automat minimalny ma postać
| | ==Wielowymiarowa całka Riemanna. Test== |
|
| |
|
| <center><math>\mathcal{A}_{L}=\left( S/ \bigcap \overline \rho _i,A,f^*,[s_{0}],T/ \bigcap \overline \rho _i \right) </math>.</center>
| |
|
| |
|
| }}
| | 1111111111111111111111111111111111111111111111111111 |
|
| |
|
| Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia 3.3 z
| | ==Twierdzenie Fubiniego. Twierdzenie o zmianie zmiennych. Test== |
| wykładu 4.
| |
|
| |
|
| Algorytm działajacy w oparciu o powyższe twierdzenie na podstawie
| |
| zadanego automatu <math>A = (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
| |
|
| |
|
| <center><math> s, t Ss _{{A}} t (s T t T) (s S T t S T)</math>.</center>
| | 1212121212121212121212121212121212121212121212121212121212 |
|
| |
|
| Definiujemy pierwszą z relacji <math>{}</math>, czyli relację
| | ==Całki krzywoliniowe. Twierdzenie Greena. Test== |
| <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:
| |
|
| |
|
| <center><math>s_1 {}_i s_2 (s_1 {}_{i-1} s_2) ( a Af(s_1, a) {}_{i-1} f(s_2,a))</math>.</center> 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}=}}_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.
| |
|
| |
|
| {{algorytm|MinHopcroft - algorytm Hopcrofta minimalizacji automatu|algorytm Hopcrofta minimalizacji automatu|
| | 1414141414141414141414141414141414141414141414141414 |
| 1 Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że <math>L=L(\mathcal{A})</math>
| |
| 2 Wyjście: <math>P</math> - podział zbioru <math>S</math> przez prawą kongruencję automatową
| |
| 3 <math>P \leftarrow \{T, S \backslash T\}</math>; <math>\triangleright</math><math>P</math> jest zbiorem rozłącznych podzbiorów <math>S</math>
| |
| 4 '''if''' <math>|T|<|S \backslash T|</math> '''for'''
| |
| 5 '''for''' '''each '''<math>a \in A</math> '''do'''
| |
| 6 '''włóż'''<math>(\mathcal{L}, (T, a))</math>;
| |
| 7 '''end''' '''for'''
| |
| 8 '''else'''
| |
| 9 '''for''' '''each''' <math>a \in A</math> '''do'''
| |
| 10 '''włóż''' <math>(\mathcal{L},(S \backslash T, a))</math>;
| |
| 11 '''end''' '''for'''
| |
| 12 '''end''' '''if'''
| |
| 13 '''while''' <math>\mathcal{L} \neq \emptyset</math> '''do'''
| |
| 14 <math>(Y, a) \leftarrow </math> '''zdejmij''' <math>(\mathcal{L})</math>;
| |
| 15 <math>\mathcal{X} \leftarrow \{X \in P:\ |X \slash \rho^a_Y| =
| |
| 2\}</math>;
| |
| 16 '''for''' '''each''' <math>X \in \mathcal{X}</math> '''do'''
| |
| 17 '''for''' '''each''' <math> b \in A</math> '''do'''
| |
| 18 <math>\{X_1, X_2\} \leftarrow X \slash \rho^a_Y</math>; <math>\triangleright </math><math>X \slash \rho^a_Y</math> zawiera dwie klasy abstrakcji
| |
| 19 <math>P \leftarrow (P \backslash X) \cup X_1 \cup X_2</math>;
| |
| 20 '''if''' <math>(X, b) \in \mathcal{L}</math> '''then'''
| |
| 21 <math>\mathcal{L} \leftarrow \mathcal{L} \backslash (X, b)</math>; <math>\triangleright</math> zdejmij z <math>\mathcal{L}</math> dokładnie parę <math>(X, b)</math>
| |
| 22 '''włóż'''<math>(\mathcal{L},(X_1,b))</math>;
| |
| 23 '''włóż'''<math>(\mathcal{L},(X_2,b))</math>;
| |
| 24 '''else'''
| |
| 25 '''if''' <math>|X_1|<|X_2|</math> '''then'''
| |
| 26 '''włóż'''<math>(\mathcal{L},(X_1,b))</math>;
| |
| 27 '''else'''
| |
| 28 '''włóż'''<math>(\mathcal{L},(X_2,b))</math>;
| |
| 29 '''end''' '''if'''
| |
| 30 '''end''' '''if'''
| |
| 31 '''end''' '''for'''
| |
| 32 '''end''' '''for'''
| |
| 33 '''end''' '''while'''
| |
| 34 '''return'''
| |
| }}
| |
|
| |
|
| | | ==Równania różniczkowe zwyczajne -- przegląd metod rozwiązywania. Test== |
| {{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>
| |
