Test GR: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 80 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
{theor}{TWIERDZENIE}[section]
<quiz type="exclusive">
{rem}{UWAGA}[section]
{corol}{WNIOSEK}[section]
{fact}{FAKT}[section]
{ex}{PRZYKŁAD}[section]
{defin}{DEFINICJA}[section]
{lem}{LEMAT}[section]


{prf}{DOWÓD}


{algorithm}{Algorytm}
</quiz>


{procedure}{Procedura}


{ Algorytmy konstrukcji automatu minimalnego }
------------------------------


; Wprowadzenie
:  W  tym wykładzie podamy  algorytmy konstrukcji  automatu minimalnego
i twierdzenia dowodzące ich poprawności.<br>


; Słowa kluczowe
1111111111111111111111111111111111111111111
:  automat minimalny, pochodna Brzozowskiego, algorytmy
minimalizacji.


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


Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, a  <math>\; u \in A^* \;</math>  dowolnym
1111111111111111111111111111111111111111111
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.


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>\aligned\nonumber u^{-1}(L_1 \cup L_2) & = & u^{-1}L_1 \cup u^{-1}L_2, \\
22222222222222222222222222222222222222222
\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]||
==Ciągi w przestrzeniach metrycznych. Test==


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
3333333333333333333333333333333333333333333333333333333333333
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>


Rozpisując z definicji lewą stronę tej równoważności, otrzymujemy,
==Norma. Iloczyn skalarny. Test==
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
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
444444444444444444444444444444444444444444444444444444444444444
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 ----
==Ciągi i szeregi funkcyjne. Szereg Taylora. Test==


Obliczone języki określające stany automatu minimalnego to
<quiz>
elementy monoidu syntaktycznego języka <math>L</math>.
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>


---- dla dociekliwych - end ----
  tak, nie, nie


Automatem minimalnym dla automatu <math>\mathcal{A}=(S, A, f, s_0, T)</math>
<quiz>
będzie zatem automat
Dany jest ciąg funkcyjny <math>\{f_n\}</math> gdzie
<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>,
<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>s_0^L = 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>


* <math>T_L = \{u^{-1}L:\ u \in L\}</math>,
  nie, tak, nie


* <math>f_L(u^{-1}L,a) = a^{-1}(u^{-1}L)=(ua)^{-1}L</math>.
<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>


Jeśli zdefiniujmy odwzorowanie <math>\nu: S \rightarrow S_L</math>, kładąc:
  nie, nie, tak
<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:


<center><math>\beginCD
<quiz>
s @>{a}>> s' @. \ \ \ \ \mbox{ w } \mathcal{A} \\
Dany jest szereg <math>\sum_{n=1}^{\infty}\frac{\sin nx}{2^n(x^2+1)}, \ x\in \mathbb{R}</math> Ten szereg jest
@V{\nu}VV  @V{\nu}VV \\
<wrongoption>zbieżny jednostajnie do funkcji <math>f(x)\equiv 0</math></wrongoption>
u^{-1}L @>{a}>> (ua)^{-1}L @. \ \ \ \ \mbox{ w } \mathcal{A}_L.
<rightoption>zbieżny jednostajnie do funkcji <math>f</math> takiej, że <math>0<f(x)<3</math></rightoption>
\endCD  </math></center>
<wrongoption>zbieżny jednostajnie do funkcji <math>f(x)=\frac{1}{2(x^2+1)}</math></wrongoption>
</quiz>


Formalny zapis algorytmu przedstawiony jest poniżej.
  nie, tak, nie


{{Minimalizuj1} - algorytm minimalizacji
<quiz>
wykorzystujący pochodne Brzozowskiego}  
Funkcja <math>
[1]
    f(x):=\sum_{n=1}^{\infty}\frac{\sqrt[n]{x}}{n(n+1)(x^2+1)}</math>
Wejście: <math>\mathcal{A}=(S, A, f, s_0, T)</math> - automat taki, że
Granica <math>\lim_{x\to 3}f(x)</math> wynosi
<math>L=L(\mathcal{A})</math>
<rightoption><math>\frac{1}{10}</math></rightoption>
<wrongoption><math>\sqrt{3}</math></wrongoption>
<wrongoption><math>0</math></wrongoption>
</quiz>


Wyjście: automat minimalny <math>\mathcal{A}'=(S_L, A, f_L, s_L,
  tak, nie, nie
T_L)</math> dla <math>\mathcal{A}S_L \leftarrow \{L\}</math>;


'''włóż'''<math>(\mathcal{L},L)</math>;
<quiz>
Szereg <math>\sum_{n=1}^{\infty}\frac{1}{n(x^4+4)}</math> jest
<wrongoption>zbieżny punktowo</wrongoption>
<wrongoption>zbieżny jednostajnie </wrongoption>
<rightoption>rozbieżny</rightoption>
</quiz>


{<math>\mathcal{L} \not =</math>}
  nie, nie, tak


<math>M \leftarrow </math> '''zdejmij'''<math>(\mathcal{L})</math>;
<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>


{'''each''' <math>a \in A</math>}
  nie, nie, tak


<math>N \leftarrow a^{-1}M</math>;
<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>


{<math>N \cap S_L = </math> }
  nie, tak, nie


<math>S_L \leftarrow S_L \cup \{N\}</math>;
<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>


'''włóż'''<math>(\mathcal{L},N)</math>;
  tak, nie, nie


{'''each''' <math>M \in S_L</math>}
5555555555555555555555555555555555555555555555555555


{'''each''' <math>a \in A</math>}
==Szereg potęgowy. Trygonometryczny szereg Fouriera. Test==


<math>f_L(M,a) \leftarrow a^{-1}M</math>;


<math>s_L \leftarrow L</math>;
101010101010101010101010101010101010101010101010101010101010


<math>T_L \leftarrow \{u^{-1}L:\ u \in L\}</math>;
==Wielowymiarowa całka Riemanna. Test==


<math>\mathcal{A}'</math>;


Funkcja '''zdejmij'''<math>(\mathcal{L})</math>, występująca w linii 6.,
1111111111111111111111111111111111111111111111111111
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]||
==Twierdzenie Fubiniego. Twierdzenie o zmianie zmiennych. Test==


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
1212121212121212121212121212121212121212121212121212121212


}}
==Całki krzywoliniowe. Twierdzenie Greena. Test==


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 -----
1414141414141414141414141414141414141414141414141414


Algorytm oblicza również monoid syntaktyczny języka <math>L </math>.
==Równania różniczkowe zwyczajne -- przegląd metod rozwiązywania. Test==
 
---- 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>

Aktualna wersja na dzień 22:12, 11 wrz 2023




1111111111111111111111111111111111111111111


1111111111111111111111111111111111111111111


22222222222222222222222222222222222222222

Ciągi w przestrzeniach metrycznych. Test

3333333333333333333333333333333333333333333333333333333333333

Norma. Iloczyn skalarny. Test

444444444444444444444444444444444444444444444444444444444444444

Ciągi i szeregi funkcyjne. Szereg Taylora. Test

Dany jest ciąg funkcyjny {fn} gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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} dla n∈ℕ Ciąg ten jest

zbieżny punktowo do f(x)≡0

zbieżny jednostajnie do f(x)≡0

zbieżny punktowo do funkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle f(x)= \left\{ \begin{array} {lll} 1 & \text{dla} & x\geq 1\\ 0 & \text{dla} & x<0 \end{array} \right} 

 tak, nie, nie

Dany jest ciąg funkcyjny {fn} gdzie

fn(x)={1−n−x1+n−xdlax>02−nx2+nxdlax<00dlax=0 dla  n=1,2,…

Ten ciąg funkcyjny jest

zbieżny jednostajnie

zbieżny punktowo ale nie jednostajnie

rozbieżny 

 nie, tak, nie

Dany jest ciąg funkcyjny fn(x)=xn dla x≥0 Ten ciąg

jest zbieżny punktowo i jego granica jest ciągła

jest zbieżny jednostajnie i jego granica jest ciągła

jest zbieżny punktowo i jego granica nie jest ciągła 

 nie, nie, tak

Dany jest szereg ∑n=1∞sin⁡nx2n(x2+1), x∈ℝ Ten szereg jest

zbieżny jednostajnie do funkcji f(x)≡0

zbieżny jednostajnie do funkcji f takiej, że 0<f(x)<3

zbieżny jednostajnie do funkcji f(x)=12(x2+1) 

 nie, tak, nie

Funkcja f(x):=∑n=1∞xnn(n+1)(x2+1) Granica limx→3f(x) wynosi

110

3

0 

 tak, nie, nie

Szereg ∑n=1∞1n(x4+4) jest

zbieżny punktowo

zbieżny jednostajnie

rozbieżny 

 nie, nie, tak

Czwarty z kolei wyraz rozwinięcia w szereg Maclaurina funkcji f(x)=cos⁡2x to

−266!

266!x6

−445x6 

 nie, nie, tak

Szósty z kolei wyraz rozwinięcia w szereg Taylora funkcji f(x)=12+x o środku w x0=0 wynosi

−164x6

−164x5

12x6 

 nie, tak, nie

Sumujemy cztery kolejne wyrazy rozwinięcia w szereg Taylora funkcji x ośrodku w x0=1 Współczynnik przy x wynosi

1516

516

116 

 tak, nie, nie

5555555555555555555555555555555555555555555555555555

Szereg potęgowy. Trygonometryczny szereg Fouriera. Test

101010101010101010101010101010101010101010101010101010101010

Wielowymiarowa całka Riemanna. Test

1111111111111111111111111111111111111111111111111111

Twierdzenie Fubiniego. Twierdzenie o zmianie zmiennych. Test

1212121212121212121212121212121212121212121212121212121212

Całki krzywoliniowe. Twierdzenie Greena. Test

1414141414141414141414141414141414141414141414141414

Równania różniczkowe zwyczajne -- przegląd metod rozwiązywania. Test

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Test_GR&oldid=82477”