Test GR3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Gracja (dyskusja | edycje)
4759 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
==Wyrażenia regularne==
{stre}{Streszczenie}
{{definicja|1.1||
{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}


Niech <math>{A}</math> będzie skończonym alfabetem. Rodzina <math>\mathcal{REG}(A^{*}) </math> '''języków regularnych''' nad alfabetem <math>A</math>  to najmniejsza, w sensie inkluzji, rodzina <math>\mathcal{R} </math> języków zawartych w  <math>A^*</math> taka, że:
{}
{}


: (1) <math>\emptyset \in\mathcal{R} </math>, <math>\forall a \in A \;\;\; \{ a \} \in\mathcal{R} </math>
{theor}{TWIERDZENIE}[section]
{rem}{UWAGA}[section]
{corol}{WNIOSEK}[section]
{fact}{FAKT}[section]
{ex}{PRZYKŁAD}[section]
{defin}{DEFINICJA}[section]
{lem}{LEMAT}[section]


: (2) jeśli <math>X, Y \in\mathcal{R} </math>, to <math>X \cup Y, \;\; X \cdot Y \;\; \in\mathcal{R} </math>
{prf}{DOWÓD}


: (3) jeśli <math> X \in\mathcal{R} </math>, to <math>X^* = \bigcup_{n=0} ^\infty X^n \in\mathcal{R} </math>
{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.<br>
 
; Słowa kluczowe
:  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
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, \\
\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]||
 
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>.
}}
}}
Wprost z definicji wynika, że <math>\left\{ 1\right\} =\emptyset ^{*}\in \mathcal{R} </math> oraz że dla dowolnego języka regularnego zachodzi równość <math>X\in \mathcal{R} </math> jest


<center><math>X^{+}=\bigcup ^{\infty }_{n=1}X^{n}=X\cdot X^{*}\in \mathcal{R}.</math></center>
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>


Wprowadzona w ten sposób definicja rodziny języków regularnych wymaga
Rozpisując z definicji lewą stronę tej równoważności, otrzymujemy,
uzasadnienia faktu, iż definiowany obiekt, definiowana rodzina, istnieje. Zauważmy więc, że warunki 1-3 definicji 1.1 spełnia na przykład rodzina <math>\mathcal{P}(A^{*}) </math> wszystkich podzbiorów  <math>A^*</math>, a zatem klasa takich rodzin nie jest pusta. Ponadto łatwo możemy stwierdzić, że jeśli rodziny <math>\mathcal{R}_{1},\: \mathcal{R}_{2} </math> spełniają warunki 1-3  powyższej definicji, to rodzina <math>\mathcal{R}_{1}\cap \mathcal{R}_{2} </math> również spełnia te warunki. Stąd możemy wyprowadzić wniosek, że najmniejsza rodzina spełniającą te warunki, to przecięcie
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>


<center><math>\mathcal{REG}(A^{*})=\bigcap \mathcal{R},</math></center>
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.


po wszystkich rodzinach <math>\mathcal{R} </math> spełniających warunki 1-3 definicji 1.1.
Pierwszy z przedstawianych algorytmów będzie konstruował automat
Zauważmy, że w świetle powyższej definicji fakt, że <math>X \in\mathcal{REG}(A^{*}) </math> oznacza, że <math>X</math> można
minimalny, wyznaczając prawą kongruencję automatową poprzez
uzyskać z liter alfabetu i zbioru pustego <math>\emptyset</math> poprzez zastosowanie wobec tych "elementarnych klocków" skończonej liczby działań: sumy, katenacji i gwiazdkowania. Na odwrót, każdy zbiór otrzymany w ten sposób jest elementem rodziny <math>\mathcal{REG}(A^{*}) </math>. Ta obserwacja prowadzi do pojęcia wyrażeń regularnych, formalnego zapisu języków regularnych.
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.


{{definicja|1.2||
---- dla dociekliwych - start ----


Niech <math>{A}</math> będzie alfabetem, a zbiór <math>\{+ , \star , \emptyset , (,)\}</math> alfabetem  rozłącznym z <math>{A}</math>. Słowo <math>{\bf \alpha} \in {\bf (}A \cup \{ + , \star , \emptyset , (,)\}{\bf )}^*</math> jest '''wyrażeniem regularnym ''' nad alfabetem <math>{A}</math> wtedy i tylko wtedy, jeśli:
Obliczone języki określające stany automatu minimalnego to
elementy monoidu syntaktycznego języka <math>L</math>.


: (1) <math>{\bf \alpha} = \emptyset</math>
---- dla dociekliwych - end ----
: (2) <math>{\bf \alpha} = a \in A \;\; ({\bf \alpha}</math> jest literą)


: (3) <math>{\bf \alpha}</math> jest w postaci <math> ({\bf \beta} + {\bf \gamma}), ({\bf \beta} {\bf \gamma} ), {\bf \gamma} ^* </math>, gdzie <math> {\bf \beta}, {\bf \gamma} </math>są wyrażeniami regularnymi nad alfabetem <math>{A}</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>
gdzie:


Przyjmujemy oznaczenia:  
* <math>S_L=\{u^{-1}L:\ u \in A^*\}</math>,


<center><math>\emptyset ^{*}=1 \;\;\text{ oraz }\; \alpha ^{*}\alpha =\alpha ^{+}. </math></center>
* <math>s_0^L = L </math>,
}}
 
Rodzinę wyrażeń regularnych nad alfabetem  <math>{A}</math> oznaczamy symbolem <math>\mathcal{WR} </math>. Łatwo zauważyć związek pomiędzy wyrażeniami regularnymi oraz wprowadzoną wcześniej rodziną <math>\mathcal{REG}(A^{*}) </math>, regularnych języków wolnego monoidu <math>A^{*} </math>. Związek ten ustala poniższa definicja.
* <math>T_L = \{u^{-1}L:\ u \in L\}</math>,
{{definicja|1.3||
 
* <math>f_L(u^{-1}L,a) = a^{-1}(u^{-1}L)=(ua)^{-1}L</math>.
 
Jeśli zdefiniujmy odwzorowanie <math>\nu: S \rightarrow S_L</math>, kładąc:
<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
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.
 
{{Minimalizuj1} - algorytm minimalizacji
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,
T_L)</math> dla <math>\mathcal{A}S_L \leftarrow \{L\}</math>;
 
'''włóż'''<math>(\mathcal{L},L)</math>;
 
{<math>\mathcal{L} \not =</math>}
 
<math>M \leftarrow </math> '''zdejmij'''<math>(\mathcal{L})</math>;
 
{'''each''' <math>a \in A</math>}
 
<math>N \leftarrow a^{-1}M</math>;
 
{<math>N \cap S_L = </math> }
 
<math>S_L \leftarrow S_L \cup \{N\}</math>;


'''Wartościowaniem wyrażenia regularnego''' nazywamy odwzorowanie
'''włóż'''<math>(\mathcal{L},N)</math>;


<center><math>|\: \: |:\mathcal{WR}\longrightarrow \mathcal{P}(A^{*})</math></center>
{'''each''' <math>M \in S_L</math>}


określone następująco:
{'''each''' <math>a \in A</math>}


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


: (2) <math>\mid a \mid = \{ a \} </math>
<math>s_L \leftarrow L</math>;


: (3) <math>\mid ({\bf \alpha} + {\bf \beta})\mid = \mid {\bf \alpha} \mid \cup \mid {\bf \beta} \mid</math> <br>
<math>T_L \leftarrow \{u^{-1}L:\ u \in L\}</math>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math> \mid ({\bf \alpha} {\bf \beta}) \mid = \mid {\bf \alpha} \mid \cdot \mid {\bf \beta} \mid </math><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>\mid {\bf \alpha}^* \mid = \mid {\bf \alpha} \mid ^*</math>
}}
Odwzorowanie określające wartość wyrażenia regularnego nie jest, jak można zauważyć,
iniekcją. Oznacza to, że różne wyrażenia regularne mogą mieć tę samą wartość, czyli określać ten sam język regularny. Prostym przykładem tego faktu  są wyrażenia regularne
<math>a^*</math> oraz <math>(a^*)^*</math>.  Zwróćmy uwagę na wartość wyrażenia regularnego oznaczonego symbolem <math>1</math>.
Jest mianowicie <center><math> \mid 1 \mid = \mid \emptyset^* \mid = \mid \emptyset \mid^* = \emptyset^* = \{1\} </math></center>
Wprowadza się następującą relację równoważności w rodzinie wyrażeń regularnych.


{{definicja|1.4||
<math>\mathcal{A}'</math>;


Wyrażenia regularne <math> {\bf \alpha} , {\bf \beta} </math> nazywamy '''równoważnymi''' i oznaczamy  <math>{\bf \alpha} = {\bf \beta} </math>, jeśli <math> \mid {\bf \alpha} \mid = \mid {\bf \beta} \mid </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>.


Problem równoważności wyrażeń regularnych jest rozstrzygalny i jest PSPACE-zupełny. Wrócimy do tego problemu w kolejnych wykładach.
{{cwiczenie|[Uzupelnij]||


Oto przykłady równoważnych wyrażeń regularnych
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>


<center><math>\aligned\alpha_1 + \alpha_2 & = & \alpha_2+ \alpha_1\\ (\alpha_1 + \alpha_2) +\alpha_3 & = & \alpha_1+ (\alpha_2 + \alpha_3) \\ (\alpha_1 \alpha_2) \alpha_3 & = & \alpha_1 (\alpha_2 \alpha_3) \\ (\alpha_1 + \alpha_2) \alpha_3 & = & \alpha_1\alpha_3 + \alpha_2 \alpha_3 \\ \alpha_1 ( \alpha_2 +\alpha_3) & = & \alpha_1 \alpha_2 + \alpha_1 \alpha_3 \\ (\alpha^*)^* & = & \alpha^*\\ (\alpha^*_1 \alpha^*_2)^* & = & (\alpha_1 + \alpha_2)^*\\ (\alpha^+ + 1) & = & \alpha^*  \endaligned</math></center>
RYSUNEK ja-lekcja5-w-rys1


gdzie <math>\alpha ,\alpha _{1},\alpha _{2},\alpha _{3}\in \mathcal{WR} </math>.
}}
}}
Wprost z definicji wyrażenia regularnego wynika następujaca równoważność:


{{fakt|1.1||
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>L\in \mathcal{REG}(A^{*})  \Longleftrightarrow L = \mid {\bf \alpha} \mid </math> dla pewnego <math>{\bf \alpha} \in\mathcal{WR} </math>.
</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>


Wyrażenia regularne dają bardzo wygodne narzędzie zapisu języków należących do rodziny <math>\mathcal{REG}(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}
Np. język  nad alfabetem <math>\{ a,b\}</math> złożony ze wszystkich słów zaczynających się lub kończących na literę <math>{a}</math> zapisujemy jako <math>a(a+b)^* +(a+b)^*a</math>.<br> Z kolei wyrażenie regularne <math>a^+ b^+</math> oznacza język <math>L=\{a^nb^m : n,m\geq 1\}</math>.
Dla dalszego uproszczenia zapisu przyjmiemy w naszym wykładzie następującą umowę. Jeśli język <math>L</math> jest wartością wyrażenia regularnego <math>{\alpha}</math>, czyli <math>L= \mid \alpha \mid</math>, to będziemy zapisywać ten fakt jako <math>L= \alpha</math>. Będziemy zatem mówić w dalszym ciągu wykładu o ''języku <math>{\alpha}</math>.'' Z tych samych powodów, dla dowolnego alfabetu <math>A=\{a_1,.....,a_n\}</math> będziemy używać zapisu <math>A</math> w miejsce <math>a_1 +.....+a_n</math>.


Zauważmy na koniec rozważań o wyrażeniach regularnych, że dość prosty w zapisie język <math>L=\{a^nb^n : n\geq 1\}</math> nie należy do rodziny <math>\mathcal{REG}(A^{*})</math> i nie można go zapisać przy pomocy wyrażeń regularnych.
</math></center>{A}_{L}<nowiki>=</nowiki>( S/_{ { }_{i}},A,f^{*},[s_{0}],T/_{ { }_{i}}) .<center><math>


{{uwaga|[Dla dociekliwych]|dociek|Kończąc ten fragment wykładu poświęcony wyrażeniom regularnym warto wspomnieć o problemie "star height", czyli głębokości zagnieżdżenia gwiazdki w wyrażeniu regularnym. Mając wyrażenia regularne <math>\alpha ,\alpha _{1},\alpha _{2}\in \mathcal{WR} </math> głębokość zagnieżdżenia gwiazdki definiuje się jako liczbę <math>sh(\alpha ) </math> równą <math>0 </math>, gdy <math>\alpha  </math> jest literą z alfabetu lub zbiorem pustym, równą <math>max\{i,j\}, </math> gdy <math>\alpha =\alpha _{1}\cup \alpha _{2} </math> lub <math>\alpha =\alpha _{1}\cdot \alpha _{2} </math> i <math>sh(\alpha _{1})=i </math>, <math>sh(\alpha _{2})=j </math> oraz równą <math>i+1 </math> dla <math>\alpha =(\alpha _{1})^{*} </math>. Głębokość zagnieżdżenia gwiazdki dla języka regularnego <math>L </math> określa się jako najmniejszą liczbę <math>sh(L)=sh(\alpha ) </math>, gdzie <math>\alpha  </math> jest wyrażeniem regularnym reprezentującym język <math>L </math>. Głębokość zagnieżdżenia gwiazdki jest więc jakby miarą złożoności pętli występujących w automacie rozpoznającym język <math>L </math>. Ustalono, że dla alfabetu złożonego z jednej litery głębokość zagnieżdżenia gwiazdki jest równa co najwyżej '''1''' oraz że dla alfabetu o co najmniej dwóch literach dla dowolnej liczby <math>k\in \Bbb N </math> można wskazać język regularny <math>L </math> taki, że <math>sh(L)=k </math>. Problemem otwartym pozostaje określenie algorytmu  określającego głębokość zagnieżdżenia gwiazdki dla dowolnego języka  w klasie języków regularnych.
\endtheor


}}
Dowód tego twierdzenia przebiega analogicznie do dowodu twierdzenia 3.3 z
wykładu 4.


==Prawa kongruencja syntaktyczna i kongruencja syntaktyczna==
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.


Opis języka regularnego za pomocą wyrażeń regularnych jest bardzo wygodny,
\newpage
ale nie jedyny. W kolejnych wykładach będziemy wprowadzać inne reprezentacje
języków regularnych, takie jak automaty czy gramatyki. Pojęcia, które wprowadzimy
teraz są również narzędziami dla opisu i badań własności języków regularnych. W
szczególności służą do konstrukcji możliwie najprostszego automatu rozpoznającego
dany język regularny, zwanego automatem minimalnym.


Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem. W monoidzie <math>\; A^* \;</math> wprowadzamy następujące
\beginalgorithm
dwie relacje:
\caption{\textsc{Minimalizuj2} -- algorytm minimalizacji automatu
wykorzystujący stabilizujący się ciąg relacji}


# '''prawą kongruencję syntaktyczną'''  <math>\; P_L^r , \;</math> przyjmując<br>
\beginalgorithmic [1]
dla dowolnych słów <math>u, v \in A^* </math> {}<br>
\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat taki, że
<math>u \; P_L^r \; v \;\; \mbox{ wtedy i tylko wtedy, gdy
</math>L<nowiki>=</nowiki>L({A})<math>.
spełniony jest warunek}</math> <center><math> \forall w \in A^* \;\; uw \in L \; \Leftrightarrow \; vw \in L, </math></center>


# '''kongruencję syntaktyczną'''  <math>\; P_L , \;</math> przyjmując <br>
\STATE Wyjście: automat minimalny </math>{A}'<nowiki>=</nowiki>(S',A',f', s_0',
dla dowolnych <math>u, v \in A^* </math>{}<br>
T')<math> dla </math>{A}<math>.
<math>u \; P_L \; v \;\; \mbox{ wtedy i tylko wtedy, gdy spełniony jest warunek} </math> <center><math> \forall w_1, w_2 \in A^* \;\; w_1uw_2 \in L \; \Leftrightarrow \; w_1vw_2 \in L. </math></center>


Łatwo stwierdzić, że nazwy wprowadzonych relacji pokrywają się z ich własnościami, to
\STATE </math>{}_1_{{A}}<math>;
znaczy relacja <math>\; P_L^r , \;</math>
jest rzeczywiście prawą kongruencją, a <math>\; P_L , \;</math> kongruencją.


{{cwiczenie|[Uzupelnij]||
\STATE </math>i  1<math>;


Niech <math>A=\{ a,b\}</math> będzie alfabetem.
\REPEAT


# Dla języka <math>L=a^+b^+ </math> relacja
\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>;


## <math>P_L^r</math> ma <math>4</math> klasy równoważności:
\STATE </math>i  i+1<math>;
<math>\;\;L, \;\;A^*baA^*+b^+,\;\; a^+, \;\;1</math>


## <math>P_L</math> ma <math>5</math> klas równoważności:
\STATE \textbf{empty}</math>({}_i)<math>  
<math>L, \;\;A^*baA^*,\;\;b^+,\;\; a^+, 1</math>


# Dla języka <math>L=\{a^nb^n : n\geq 1\}</math> obie relacje mają nieskończony indeks
\FOR{\textbf{each} </math>(s_1,s_2) S S<math>}


## dla <math>P_L^r</math>  klasami równoważności są zbiory <br>
\STATE flag\textbf{true};
<math>L_i =\{a^nb^{n-i} : n\geq i,n \geq 1\}</math> dla <math>i \in \mathbb{N}_0</math>, <math>A^* \setminus\bigcup_{i=0}^\infty L_i</math>


## dla <math>P_L</math>  klasami równoważności są zbiory <br>
\FOR{\textbf{each} </math>a A<math>}
<math>L_i =\{a^nb^{n-i} : n\geq i,n \geq 1\}</math> dla <math>i \in \mathbb{N}_0</math>,<br>
<math>L'_i =\{a^{n-i}b^n : n\geq i,n \geq 1\}</math> dla <math>i \in \mathbb{N}</math> <br>
<math>A^* \setminus[\bigcup_{i=1}^\infty (L_i\cup L'_i )\cup L_0 ]</math> 


}}
\IF{\textbf{not} </math>f(s_1, a) {}_{i-1} f(s_2,a)<math>}


Udowodnimy następujące własności relacji <math>\; P_L^r \;</math> oraz <math>\; P_L \;</math>.
\STATE flag\textbf{false};


Prawa kongruencja syntaktyczna <math>\; P_L^r \;</math> jest największą w sensie inkluzji spośród wszystkich
\ENDIF
prawych kongruencji <math>\rho  </math> takich, że <center><math>L = \bigcup_{w\in L}[w]_\rho </math></center>
Kongruencja syntaktyczna <math>\; P_L \;</math> jest największą w sensie inkluzji spośród wszystkich
kongruencji <math>\rho  </math> takich, że <center><math>L = \bigcup_{w\in L}[w]_\rho </math></center>


Dowód przeprowadzimy dla prawej kongruencji syntaktycznej. Uzasadnienie tezy dla
\ENDFOR
kongruencji <math>\; P_L \;</math> przebiega podobnie.
Niech  <math>\;\rho \;</math> będzie dowolną prawą kongruencją spełniającą założenia i
niech <math>u\rho v </math>. Zatem dla każdego <math>w\in A^{*} </math> jest


<center><math>uw\rho vw \Rightarrow (uw\in L\Leftrightarrow vw\in L) \Leftrightarrow u\; P_L^r \; v. </math></center>
\IF{flag=\textbf{true} \textbf{and} </math>s_1 {}_{i-1} s_2<math>}


W konsekwencji <math>\rho \subseteq P_L^r.</math> W
\STATE </math>{}_{i} {}_{i}  
szczególności więc dla dowolnego <math> u \in A^*</math> ma miejsce inkluzja <math>[u]_\rho \; \subseteq \; [u]_{P_L^r}.</math> Zatem <math>L\subset \bigcup _{w\in L}[w]_{P^{r}_{L}} </math>.
(s_1,s_2)<math>;
Aby udowodnić inkluzję w stronę przeciwną ustalmy dowolne <math>\; u \in L \;</math> i niech <math>v \in [u]_{P_L^r}.</math>
Przyjmując <math>\; w =1 \;</math> w definicji&nbsp;[[##d1|Uzupelnic d1|]] relacji <math>\; {P_L^r} \;</math>  otrzymamy równoważność
<math>\; u \in L \; \Leftrightarrow \; v \in L \;.</math> A więc <math>\; v \in L \;.</math><br>


<math>\diamondsuit</math>   
\ENDIF


Jeśli język <math>L </math> jest regularny, to  relacja <math>\; P_L^r \;</math> jest największą
\ENDFOR
w sensie inkluzji spośród wszystkich
prawych kongruencji takich, że język <math>L</math> jest sumą jej pewnych klas równoważnosci
a relacja <math>\; P_L \;</math> jest
największą w sensie inkluzji
spośród wszystkich kongruencji spełniających analogiczny warunek.
Obie relacje mają skończony indeks, czyli dzielą wolny monoid <math>A^*</math> na
skończoną liczbę klas równoważności.


---- dla dociekliwych - start ----
\UNTIL{</math>{}_i <nowiki>=</nowiki> {}_{i-1}<math>}


Pojęcie, które wprowadzimy teraz - monoid syntaktyczny języka - wiąże teorię
\STATE </math>S' S  {}_i<math>;
języków formalnych, a
w szczególności teorię języków rozpoznawalnych, z&nbsp;teorią półgrup. Związek ten
stanowi podstawę dla bardziej zaawansowanych
problemów teorii języków i automatów wykraczających poza ramy tego wykładu.


Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem. '''Monoidem syntaktycznym'''
\FOR{\textbf{each} </math>[s]_{{}_i}  S
języka <math>\; L \;</math> nazywamy strukturę ilorazową
{}_i<math>}


<center><math>M(L) = A^*/P_L .</math></center>
\FOR{\textbf{each} </math>a  A<math>}


Dualnie, tworząc iloraz <math>S(L) = A^+/P_L</math> wprowadza się pojęcie półgrupy syntaktycznej
\STATE </math>f'([s]_{{}_i},a)  
języka <math>\; L \;</math>. Oba wprowadzone tu pojęcia zilustrowane bedą w trakcie dalszych
[f(s,a)]_{{}_i}<math>;
rozważań.


---- dla dociekliwych - end ----
\ENDFOR


==AUTOMAT MINIMALNY==
\ENDFOR


Określenie języka rozpoznawalnego postuluje istnienie automatu o skończonej
\STATE </math>s_0' [s_0]_{{}_i}<math>;
liczbie stanów działającego w odpowiedni sposób. Należałoby zatem wskazać algorytm
budowy takiego automatu dla języka rozpoznawalnego. Oczywiście interesuje nas algorytm
prowadzący do automatu o możliwie najprostszej postaci. Najprostsza postać, w tym kontekście,
oznacza najmniejszą liczbę stanów.


Automat <math>\mathcal{A} </math></center><nowiki>=</nowiki> (S,A,f,s_0,T) <math> rozpoznający język </math>L<math>
\STATE </math>T'  [t]_{{}_i}:t  T<math>;
na\-zy\-wa\-my \textbf{automatem minimalnym}\index{automat minimalny},
jeśli posiada najmniejszą licz\-bę stanów spośród wszystkich automatów
rozpoznają\-cych język </math> L. <math>
\enddefin


Kwestią istnienia takiego automatu minimalnego zajmujemy się teraz. W kolejnym
\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
wykładzie przedstawimy algorytmy konstrukcji automatu minimalnego.


W poniższym twierdzeniu występuje automat ilorazowy </math>{A}_{P^{r}_{L}} <math>
\endalgorithmic
określony przez
\endalgorithm
prawą kongruencję </math>P_L^r<math>.


\begintheor
{{cwiczenie|[Uzupelnij]||


Dla dowolnego automatu </math>{A} <center><math>= (S,A,f,s_0,T) \;</math> rozpoznającego
Zminimalizujemy automat </math>{A}<nowiki>=</nowiki>(S,A,f,s_0,T)<math>, dla którego\\
język <math>\; L \subset A^* \;</math> istnieje jedyny
</math>S<nowiki>=</nowiki> s_{0},s_{1},s_{2},s_{3},s_{4},s_5 , A<nowiki>=</nowiki>a,b,
epimorfizm <math>\varphi :\mathcal{A}\longrightarrow \mathcal{A}_{P^{r}_{L}} </math>
T<nowiki>=</nowiki>s_1, s_{2},s_{4} <math>,
taki, że <math>\varphi (s_{0})=[1]_{P^{r}_{L}}. </math>
a funkcja przejść określona jest przy pomocy grafu.\\
RYSUNEK ja-lekcja5-w-rys2\\
Konstruujemy ciąg
relacji </math>{}_i<math>.


Prawa kongruencja automatowa <math>\sim _{\mathcal{A}} </math> ma
Na początku  </math>{}_1<math> dzieli </math>S<math> na dwie klasy
skończony indeks
abstrakcji; pierwsza zawiera stany końcowe, a druga -- wszystkie
i <math>L=\bigcup _{u\in L}[u]_{\sim _{\mathcal{A}}} </math>.
pozostałe, czyli uzyskujemy dwa zbiory </math>s_1,s_2,s_4<math> oraz
Zatem z twierdzenia&nbsp;[[##trr2|Uzupelnic trr2|]] wynika, że
</math>s_0, s_3, s_5<math>.


<center><math>\sim _{\mathcal{A}}\subseteq P^{r}_{L}=\sim _{\mathcal{A}_{P^{r}_{L}}}.</math></center>
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>.


Istnienie epimorfizmu <math>\; \varphi \;</math> wynika z  twierdzenia 1.1, wykład 3.
Rozważmy najpierw zbiór </math>s_1, s_2, s_4<math>. Oczywiście każde dwa
Epimorfizm ten określony jest dla dowolnego stanu <math>s\in S </math>
stany z tego zbioru są ze sobą w relacji </math>{}_1<math>.
równością <math> \varphi(s) = f^*([1]_{P_L^r},w) = [w]_{P_L^r},</math> gdzie <math>w </math> jest
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
słowem takim, że <math>f(s_0,w)=s</math>.
</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>.


Jest to jedyny epimorfizm spełniający warunki tezy dowodzonego
W analogiczny sposób można sprawdzić, że relacja </math>{}_2<math> nie
twierdzenia. Dla każdego epimorfizmu  <math>\; \psi \;</math> takiego,  
podzieli zbioru </math>s_0, s_3, s_5<math>. Ostatecznie, po pierwszym
że <math>\psi :\mathcal{A}\longrightarrow \mathcal{A}_{P^{r}_{L}} </math>
wykonaniu pętli algorytmu minimalizacji obliczyliśmy relację
i <math>\psi (s_{0})=[1]_{P^{r}_{L}} </math>  
</math>{}_2<math>, która dzieli </math>S<math> na następujące podzbiory:
mamy<br> <math>\;\forall s \in S</math> <center><math>\psi(s) = \psi(f(s_o,w)) = f^* (\psi(s_0),w) = f^* ([1]_{P_L^r},w) = [w]_{P_L^r},</math></center>  
</math></center>s_1, s_2, s_4, s_0, s_3, s_5.<center><math>
gdzie <math> f(s_0,w) = s .</math>
Tak więc <math>\; \psi = \varphi .\;\diamondsuit</math>   


Zatem udowodnione twierdzenie zapewnia nas o istnieniu automatu minimalnego, co
W kolejnym kroku obliczamy </math>{}_3<math>. Zbiór </math>s_1<math>
formułujemy w następującym wniosku.
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>.


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


<center><math>\mathcal{A}_{P^{r}_{L}}=\left( A^{*}/_{P^{r}_{L}},A,f^{*},[1]_{P^{r}_{L}},T\right), </math></center>
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>.


gdzie <math>\; T = \{ [w]_{P_L^r} \; : \; w \in L \}, \;</math> jest automatem
Podział zbioru </math>S<math> przez relację </math>{}_3<math> wygląda więc
minimalnym rozpoznającym język <math>\; L \;</math>. Oznaczać go
następująco: </math></center>s_0, s_1, s_2, s_4, s_3, s_5.<center><math>
będziemy symbolem <math>\mathcal{A}_{L} </math>.


---- dla dociekliwych - start ----
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.


Następne twierdzenie charakteryzuje monoid przejść automatu minimalnego i
Podsumowując, mamy:
podaje kolejny warunek równoważny na to,
żeby język <math>L</math> był rozpoznawany przez automat.


Niech <math>L\subset A^{*} </math> będzie dowolnym językiem.{}{}
; </math>{} _{1}<math>
:  </math>s_1, s_{2},s_{4}, s_{0},s_{3},s_5,  <math>


1. Dla dowolnego języka <math>L\in \mathcal{REC}(A^{*}) </math> monoid przejść automatu minimalnego <math>\mathcal{A}_{L} </math> jest
; </math>{} _{2}<math>
izomorficzny z monoidem syntaktycznym <math> M(L) </math> języka <math>L</math>, czyli
:  </math>s_{1},s_2,s_{4}, s_{0},s_{3},s_5,<math>


<center><math>M(\mathcal{A}_{L})\sim M(L). </math></center>
; </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


2. (tw. J.Myhill'a) Język <math>\; L \subset A^* \;</math> jest rozpoznawalny wtedy i tylko wtedy,
}}
gdy <math>\; M(L) \;</math> jest monoidem skończonym.


Dla dowodu punktu 1, wykażemy, że
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|]].


<center><math>P_{L}=Ker_{\tau _{\mathcal{A}_{L}}}, </math></center>
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>.


gdzie zgodnie z definicją dla dowolnych <math>w,u\in A^{*} </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>


<center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
\begindefin 
Stany </math>p<math> i </math>q<math> są równoważne, jeśli </math>p  q<math>.
\enddefin


<center><math>\begin{array} {c}
Jeśli stany nie są równoważne, to będziemy mówić, że są
(u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
rozróżnialne.
\tau _{\mathcal{A}_{L}}(u)([v]_{P^{r}_{L}})=\tau _{\mathcal{A}_{L}}(w)([v]_{P^{r}_{L}})\Leftrightarrow
[vu]_{P^{r}_{L}}=[vw]_{P^{r}_{L}}\Leftrightarrow\\
\Leftrightarrow \forall v,z \in A^*\;\;vuz\in L\Leftrightarrow vwz\in L \Leftrightarrow[u]_{P_{L}}=[w]_{P_{L}}
\Leftrightarrow (u,v) \in P_L\\


\end{array} </math></center>
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.


Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku
W praktyce algorytm nie wyznacza stanów równoważnych, ale stany
ma postać:  <br>
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.


RYSUNEK ja-lekcja4-w-rys1.pdf<br>
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>.


czyli <math>M(\mathcal{A}_{L})\sim M(L) </math>. <br>
\newpage
Dla dowodu punktu 2 załóżmy, że język <math>\; L \;</math> jest rozpoznawalny.
Zatem
<center><math>L = \bigcup_{w \in L} [w]_\rho ,</math></center> gdzie <math>\; \rho \;</math> jest kongruencją o skończonym indeksie.
Z twierdzenia&nbsp;[[##trr2|Uzupelnic trr2|]] wnioskujemy, że <math>\rho \subseteq P_L .</math> Oznacza to, że indeks relacji <math>\; P_L \;</math> jest
niewiększy od indeksu <math>\; \rho, \;</math> a co za tym idzie, <math>\; M(L) = A^*/P_L \;</math> jest monoidem skończonym.


Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm kanoniczny <center><math>k : A^* \longrightarrow A^*/P_L = M(L).</math></center>
\beginalgorithm 
Pokażemy, że spełnia on warunki z punktu 4 twierdzenia 1.2 z wykładu 3.  <math>M(L) \;</math> jest skończony, więc pozostaje do wykazania
\caption{\textsc{Minimalizuj3} -- algorytm minimalizacji
równość
wykorzystujący relację }
<center><math>\; L = k^{-1}(k(L)). \;</math></center> W tym celu wystarczy oczywiście udowodnić inkluzję
\beginalgorithmic [1]
<math>\; k^{-1}(k(L)) \subseteq L</math>. <br>
\STATE Wejście: </math>{A}<nowiki>=</nowiki>(S, A, f, s_0, T)<math> -- automat


<center><math>\begin{array} {c}
\STATE Wyjście: </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math> -- automat
v \in k^{-1}(k(L))\Rightarrow k(v) \in k(L)\Rightarrow\exists u \in L:k(v) = k(u) \in k(L)\Leftrightarrow\\
minimalny taki, że </math>L({A}')<nowiki>=</nowiki>L({A})<math>.
\Leftrightarrow \exists u \in L:[v]_{P_L} = [u]_{P_L}\Leftrightarrow\exists u \in L:v \in L\Leftrightarrow u\in L.\\
\end{array}  
</math></center>


Czyli <math>v\in L</math> i <math>\; L = k^{-1}(k(L))</math>.
\FOR{\textbf{each} </math>p  T<math>}
<math>\diamondsuit</math>   


---- dla dociekliwych - end ----
\FOR{\textbf{each} </math>q  S  T<math>}


Z twierdzenia [[##3.1|Uzupelnic 3.1|]] wynika, że określenie klas abstrakcji prawej kongruencji syntaktycznej
\STATE \textbf{zaznaczone}</math>[p,q] 1<math>;
<math>P^r_L</math> prowadzi do określenia  minimalnego automatu rozpoznającego  język <math>L</math>.
Prezentowane poniżej twierdzenia wskazują sposób konstrukcji prawej kongruencji syntaktycznej
dla języka <math>L </math>.


Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem, <br> a  <math>\; \Theta_L \subset A^* \times A^* \;</math>  relacją
\STATE \textbf{initialize}(</math>{L}[p,q]<math>)
równoważności o  dwóch klasach równoważności <math>L</math> i <math> A^* \setminus L</math>.
Przez <math>\; \rho_i \;</math> dla <math>\; i \in {\Bbb N} </math> oznaczmy zstępujący ciąg relacji określony następująco:


<math>\rho_1 = \Theta_L ,\;\;</math> a dla <math>\; i = 2,... </math> przyjmijmy
\ENDFOR


<math>\rho_i = \{ (u,w) \in \; A^* \times A^* \; : \; (ua,wa) \in \; \rho_{i-1} \;\;\; \forall a \in A \cup \{1\}\}.</math>
\ENDFOR


{ Wtedy <math>\;\; \bigcap \rho_i = P_L^r \;\;</math>. }
\FOR{</math>'''each'''(p,q)  (T  T)  ((S  T)
(S  T))<math>}


Na początku uzasadnimy, że <math>\; \bigcap \rho_i \;</math> jest prawą kongruencją na <math>\; A^*</math>.
\STATE \textbf{zaznaczone}</math>[p,q] 0<math>;
Załóżmy więc, że słowa <math>\; x , y \in A^* \;</math> są w relacji <math>x \; \bigcap \rho_i \;y \;</math>.
Wybierzmy
dowolne słowo <math>z\in A^{*} </math>
i niech <math>k </math> oznacza długość tego słowa. Z&nbsp;założenia
wynika, iż <math>x\, \rho _{i+k}\, y </math>, co w świetle definicji ciągu
relacji <math>\rho _{i} </math> implikuje, że <math>xz\: \rho _{i}\: yz. </math> Ponieważ
<math>i </math> jest dowolne wnioskujemy ostatecznie, że <math>xz \; \bigcap \rho_i \; yz \;,</math>
co kończy dowód faktu, że <math>\; \bigcap \rho_i \;</math> jest prawą kongruencją.


Dowiedziemy teraz równości <center><math>\bigcap \rho_i \; = \; P_L^r .</math></center>
\ENDFOR


Dla uzasadnienia inkluzji <math>\bigcap \rho_i \;\subseteq\; P_L^r</math> zauważmy, że
\FOR{</math>'''each ''' (p,q)  (T  T)  ((S  T)
jeśli <math>x \; \bigcap \rho_i \; y ,</math> to dla dowolnego <math>z\in A^{*} </math> mamy
(S  T))<math>}
<math>xz \; \bigcap \rho_i \; yz</math>, a w szczególności <math>xz \; \rho_1 \; yz.</math>
Z definicji relacji <math>\rho _{1} </math> dla dowolnego <math>z\in A^{*} </math> prawdziwa
jest równoważność <center><math>xz \in L \;\; \Leftrightarrow \;\; yz \in L.</math></center>
A więc <math>x \;\; P_L^r \;\; y </math>. Inkluzję w stronę przeciwną pokażemy, dowodząc indukcyjnie
ze względu na <math>i=1,2,... </math> , że dla dowolnych <math>\;x , y \in A^* \;</math> prawdziwa
jest następująca implikacja


<center><math>x \;\; P_L^r \;\; y \;\;\; \Longrightarrow \;\;\; x \; \rho_i \; y \;\;.</math></center>
\STATE flag\textbf{false}
Załóżmy zatem, że <math>x \;\; P_L^r \;\; y. </math>
Z definicji  <math>\; P_L^r \;</math> wynika, że dla dowolnego <math>z \in A^* </math> prawdziwa jest równoważność


<center><math> xz \in L \;\; \Leftrightarrow \;\; yz \in L.</math></center> Przyjmując <math>\; z=1 \;</math> otrzymujemy
\FOR{\textbf{each } </math>a A<math>}
żądaną własność dla <math>\rho _{1}. </math> Załóżmy teraz, że
prawdziwa jest implikacja
<center><math>x \;\; P_L^r \;\; y \;\;\; \Longrightarrow \;\; x \; \rho_i \; y.</math></center>
dla <math>i = 1,...,n-1</math> oraz dla dowolnych <math>x , y \in A^*.</math>
Stąd,
że <math>P_L^r</math> jest prawą kongruencją, wnioskujemy, że dla dowolnego <math>\; a \in A \cup \{1\} \;</math>
spełniona jest relacja <math>xa \;\; P_L^r \;\; ya .</math>
Korzystając z założenia indukcyjnego mamy
<math>xa \;\; \rho_{n-1} \;\; ya</math> dla dowolnego <math>\; a \in A \cup \{1\} \;</math>.
A to oznacza z definicji <math>\; \rho_i \;</math>, że <math>x \;\; \rho_n \;\;y </math> i kończy dowód.


<math>\diamondsuit</math>  
\IF{ \textbf{zaznaczone}</math>[f(p,a),f(q,a)]<nowiki>=</nowiki>1<math>}
\STATE flag\textbf{true};


Kolejne twierdzenie charakteryzuje relację <math>P^r_L</math> dla języka  rozpoznawalnego i orzeka, iż
\ENDIF
w przypadku języka rozpoznawalnego ciąg relacji <math>\rho_i</math>, aproksymujacych  <math>P^r_L</math>, jest
\ENDFOR
skończony.  Równoważność dwóch pierwszych warunków poniższego twierdzenia nazywana bywa często
w literaturze twierdzeniem A.Nerode.


Następujące warunki są równoważne:
\IF{flag=\textbf{true}}


# Język <math>L</math> jest rozpoznawalny
\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>;


#  Relacja <math>P^r_L</math> ma skończony indeks
\ELSE


#  Ciąg relacji <math>\rho_i</math> stabilizuje się, co oznacza, że istnieje <math>i\in {\Bbb N} </math> takie, że <center><math>\rho_i = \rho_{i+1}=....</math></center>Dla najmniejszego takiego <math>i</math> prawdziwa jest równość <math>\rho_i = P^r_L.</math>
\FOR{\textbf{each } </math>a  A<math>}


Dowód poprowadzimy według następujacego schematu:
\IF{</math>f(p,a) f(q,a)<math>}


{ [[##u1|Uzupelnic u1|]] <math>\Longleftrightarrow  </math> [[##u2|Uzupelnic u2|]]<math>\Longleftrightarrow  </math>[[##u3|Uzupelnic u3|]] }
\STATE \textbf{włóż}</math>({L}[p,q],(f(p,a),f(q,a)))<math>;


[[##u1|Uzupelnic u1|]] <math>\Longrightarrow </math> [[##u2|Uzupelnic u2|]]
\ENDIF


{ <math>P^r_L</math> jest największą w sensie inkluzji relacją spełniająca
\ENDFOR
warunki punktu 2 z&nbsp;twierdzenia 1.2, wykład 3. Z tego samego twierdzenia wynika
skończoność indeksu. }


[[##u1|Uzupelnic u1|]]<math>\Longleftarrow </math> [[##u2|Uzupelnic u2|]]
\ENDIF


Relacja <math>P^r_L</math> jest prawą kongruencją, ma skończony indeks oraz
\ENDFOR
<center><math>L = \bigcup_{w \in L}[w]_{P^r_L}.</math></center> Z twierdzenia z&nbsp;twierdzenia 1.2, wykład 3 wynika więc, że język <math>L</math> jest rozpoznawalny.


[[##u2|Uzupelnic u2|]]<math>\Longrightarrow </math> [[##u3|Uzupelnic u3|]]
\STATE </math>S'  S _<math>;\hfill
relacja  jest dopełnieniem tabeli </math>'''zaznaczone'''<math>


Dowód poprowadzimy nie wprost. Załóżmy więc, że dla każdego <math>i\in {\Bbb N} </math>
\FOR{\textbf{each} </math>[s]_{ }  S _<math>}
jest <math>\rho_i \neq \rho_{i+1}.</math> Oznacza to, że dla każdego <math>i\in {\Bbb N} </math>
indeksy relacji <math>\rho _{i} </math> tworzą ciąg silnie rosnący, to znaczy
spełniają zależność <math>ind\rho_i < ind\rho_{i+1}.</math> Ponieważ <math>ind\rho_1 = 2,</math> to dla każdego <math>i\in {\Bbb N} </math>
prawdziwa jest nierówność <math>ind\rho_i > i.</math> A&nbsp;to prowadzi do wniosku, że dla dowolnego <math>i\in {\Bbb N} </math>


<center><math>indP^r_L = ind\bigcap\rho_i >i .</math></center> Zatem indeks relacji <math>P^r_L</math> jest nieskończony, co jest sprzeczne z założeniem.
\FOR{\textbf{each} </math>a  A<math>}


[[##u2|Uzupelnic u2|]] <math>\Longleftarrow </math> [[##u3|Uzupelnic u3|]]
\STATE </math>f'([s]_{},a)  [f(s,a)]_{}<math>;


Udowodnimy indukcyjnie ze względu na <math>j</math>, że każda z relacji <math>\rho_j</math> dla <math>j=1,...,i</math>
\ENDFOR
ma skończony indeks. Oczywiście <math>ind\rho_1 = 2.</math> Załóżmy teraz, że relacja <math>\rho_j</math>
ma skończony indeks. Z definicji relacji <math>\rho_{j+1}</math> wynika,
że jej klasy równoważności powstają przez podział
klas równoważności <math>[w]_{\rho_j}</math> na skończoną liczbę klas relacji <math>\rho_{j+1}</math>
(skończona jest
liczba możliwych do spełnienia warunków prowadzących do podziału). Oznacza to, że
indeks relacji <math>\rho_{j+1}</math> jest również skończony, a więc
relacja <math>P^r_L</math> ma również skończony indeks.


<math>\diamondsuit</math>   
\ENDFOR


Wykorzystamy powyżej udowodnione własności do konstrukcji automatu minimalnego rozpoznającego
\STATE </math>s_0'  [s_0]_{}<math>;
język <math>L</math>. Warto zauważyc, iż punktem wyjścia dla tej konstrukcji jest język <math>L</math> zadany, na
przykład, poprzez wyrażenie regularne.


{{cwiczenie|[Uzupelnij]||
\STATE </math>T'  [t]_{}:t  T<math>;


Niech do języka <math>L</math> należą wszystkie słowa nad alfabetem <math>A=\{a,b\}^* </math> zaczynające się lub kończące literą <math>a</math>.
\RETURN </math>{A}'<nowiki>=</nowiki>(S', A, f', s_0', T')<math>;
Skonstruujemy minimalny automat akceptujący język <math>L</math>.


; <math>\rho _{1}</math>
\endalgorithmic
:  <math>L=aA^* +A^* a,\;\; A^{*}\setminus L =bA^*b +b+1</math>
\endalgorithm


; <math>\rho _{2}</math>
Występujaca w algorytmie procedura \textsc{Oznacz} opisana jest poniżej.
:  <math>aA^*a+a,\;\; bA^*a, \;\; bA^*b +b+1,</math>


; <math>\rho _{3}</math>
\beginalgorithm
:  <math>aA^*a+a,\;\; bA^*a, \;\; bA^*b +b, \;\;1,</math>
\beginalgorithmic [1]


Ponieważ  <math>\rho _{3}=\rho _{4}</math>, to <math>P^r_L=\rho _{3}</math> i automat minimalny ma <math>4</math> stany.<br>
\STATE \textbf{procedure} \textsc{Oznacz}</math>(p,q  S)<math>
Przyjmujemy <math>s_0 =[1]</math>, <math>s_1=bA^*a </math>, <math>s_2=aA^*a+a </math>, <math>s_3=bA^*b +b</math>
oraz <math>T=\{s_1,s_2\} </math>, a automat minimalny <math>\mathcal{A}_{L}=\left( A^{*}/_{\rho _{3}},f^{*},s_{0},T\right) </math>  
przedstawiony jest przy pomocy grafu:


RYSUNEK ja-lekcja4-w-rys2.JPG
\IF{\textbf{zaznaczone}</math>[p,q]<nowiki>=</nowiki>1<math>}
\STATE{ \textbf{return}}
\ENDIF


}}
\STATE{\textbf{zaznaczone}</math>[p,q] 1<math>}


{{cwiczenie|[Uzupelnij]||
\WHILE{\textbf{not empty}</math>({L}[p,q])<math>}
\STATE{\textsc{Oznacz}(\textbf{zdejmij}</math>({L}[p,q])<math>)}
\ENDWHILE


Dla języka <math>L=\left\{ w \in \{ a,b\}^* :\#_a w =2k, \#_b w =2l+1
\STATE \textbf{end procedure}
,\; k,l\geq 0  \right\}  </math> określimy ciąg relacji <math>{\rho}_i</math>, a
\endalgorithmic
następnie relację <math>P^{r}_{L} </math>. Umożliwi nam to, w świetle
\endalgorithm
powyższych rozważań, zbudowanie automatu minimalnego rozpoznającego
ten język. Poniżej wypisane są klasy równoważności relacji <math>\rho _{1} </math> oraz <math>\rho _{2} </math>, <math>\rho _{3}=\rho _{2} </math>, co
kończy proces obliczania relacji <math>\rho _{i} </math> i daje równość <math>\rho _{2}=P^{r}_{L} </math>.<br>


; <math>\rho _{1}</math>
Działanie algorytmu łatwo przedstawić na tabelce, która
:  <math>L, A^{*}\setminus L</math>
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.


; <math>\rho _{2}</math>
{{cwiczenie|[Uzupelnij]||
:  <math>L, L_1, L_2, L_3</math>, gdzie<br>
<math>L_1=\left\{ w \in \{ a,b\}^* :\#_a w =2k, \#_b w= 2l, \; k,l\geq 0  \right\},</math><br>
<math>L_2\left\{ w \in \{ a,b\}^* :\#_a w =2k+1, \#_b w= 2l+1, \; k,l\geq 0  \right\},</math><br>
<math>L_3=\left\{ w \in \{ a,b\}^* :\#_a w =2k+1, \#_b w= 2l, \; k,l\geq 0  \right\},</math>


Przyjmując <math>s_0 =L_1=[1]</math>, <math>s_1=L_3</math>, <math>s_2=L_2</math>, <math>s_3=L</math> oraz <math>T=\{s_3\} </math>
Zminimalizujemy automat przedstawiony na rysunku
automat minimalny <math>\mathcal{A}_{L}=\left( A^{*}/_{\rho _{2}},f^{*},s_{0},T\right)  </math>
[[##ja-lekcja5-w-rys4|Uzupelnic ja-lekcja5-w-rys4|]], używając algorytmu \textsc{Minimalizuj3}.
przedstawiony jest przy pomocy grafu:


RYSUNEK ja-lekcja4-w-rys3.JPG<br>
RYSUNEK ja-lekcja5-w-rys4


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


---- dla dociekliwych - start ----
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.


Powyższe twierdzenia podają również sposób konstrukcji
Z tabelki odczytujemy, że stanami równoważnymi są stany </math>s_1, s_5<math>,
monoidu syntaktycznego języka <math>L</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|]].


---- dla dociekliwych - end ----
RYSUNEK ja-lekcja5-w-rys6.</math>

Wersja z 12:46, 17 sie 2006

{stre}{Streszczenie} {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}

{} {}

{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⊂A* będzie dowolnym językiem, a u∈A* dowolnym słowem. Pochodną Brzozowskiego (residuum) z języka L względem słowa u nazywamy język

u−1L={w∈A*:uw∈L}.

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

Niech L1,L2⊂A* będą dowolnymi językami, a∈A dowolną literą, a u,v∈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−1L=a*b+,
b−1L=∅,
ab−1L=b*,
1−1L=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ń:
∀n∈ℕ(an)−1L=a*b+,
∀n∈ℕ(bn)−1L=∅,
∀n∈ℕ(abn)−1L=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ą:

uPrLv⟺u−1L=v−1L.

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

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−1L dla każdej litery a∈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−1X,

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,s0,T) będzie zatem automat

𝒜L=(SL,A,fL,s0L,TL),

gdzie:

  • SL={u−1L: u∈A*},
  • s0L=L,
  • TL={u−1L: u∈L},
  • fL(u−1L,a)=a−1(u−1L)=(ua)−1L.

Jeśli zdefiniujmy odwzorowanie ν:S→SL, kładąc:

ν(s)=u−1L, gdzie s=f(s0,u),

to można dowieść,

że ν jest dobrze określone, jest epimorfizmem oraz ν(s0)=s0L - porównaj twierdzenie 3.1 z wykładu 4. Prawdą jest też, iż s∈T wtedy i tylko wtedy, gdy ν(s)∈TL 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,s0,T) - automat taki, że L=L(𝒜)

Wyjście: automat minimalny 𝒜′=(SL,A,fL,sL,TL) dla 𝒜SL←{L};

włóż(ℒ,L);

{ℒ=}

M← zdejmij(ℒ);

{each a∈A}

N←a−1M;

{N∩SL= }

SL←SL∪{N};

włóż(ℒ,N);

{each M∈SL}

{each a∈A}

fL(M,a)←a−1M;

sL←L;

TL←{u−1L: u∈L};

𝒜′;

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=(SL,A,f,L,T), gdzie
SL={L,a*b+,∅,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 ρ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 } {}_1dzieliSParser 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_4orazs_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) } sitParser 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(bos_2 {}_1 s_2orazs_4 {}_1 s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle ). Ponieważ } f(s_1,b)=s_5if(s_2,b)=s_4Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a wiemy, że } s_5niejestwrelacji{}_1zs_4,zatemstanys_1is_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_1is_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 } {}_2niepodzielizbiorus_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.Mamyf(s_3, a)=f(s_5, a)orazf(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,zatems_3is_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_2if(s_3, a)=s_1,ales_2is_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_5nazbiorys_0orazs_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,anizbiorus_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)ma4Parser 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 } piqParser 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].Funkcjaempty({L}[p,q])Parser nie mógł rozpoznać (błąd składni): {\displaystyle zwraca wartość } truegdylistajestpusta,orazfalseParser 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,stanys_2, s_8orazstanys_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.}

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