|
|
| (Nie pokazano 39 wersji utworzonych przez 4 użytkowników) |
| Linia 1: |
Linia 1: |
| {theor}{TWIERDZENIE}[section]
| | --- przykładowo jak zrobić pierwsze pytanie z pierwszego modułu --- |
| {rem}{UWAGA}[section]
| |
| {corol}{WNIOSEK}[section]
| |
| {fact}{FAKT}[section]
| |
| {ex}{PRZYKŁAD}[section]
| |
| {defin}{DEFINICJA}[section]
| |
| {lem}{LEMAT}[section]
| |
|
| |
|
| {prf}{DOWÓD}
| | <quiz type="exclusive"> |
| | Dowolna kategoria składa się ze zbioru obiektów i zbioru morfizmów, które |
| | spełniają odpowiednie aksjomaty dotyczące złożenia, identyczności, |
| | dziedzin i kodziedzin morfizmów. |
| | <wrongoption>Prawda</wrongoption> |
| | <rightoption>Fałsz</rightoption> |
| | </quiz> |
| | --------------------------------------------------------------------- |
|
| |
|
| {Wyra{Z}enia regularne,<br> automat minimalny}
| |
|
| |
|
| ; Wprowadzenie
| | <quiz> |
| : W tym wykładzie określimy rodzinę języków regularnych wolnego monoidu <math>A^{*} </math> | | Zaznacz zdania prawdziwe dotyczące podłogi i sufitu: |
| oraz pewien formalny opis tych języków zwany wyrażeniami regularnymi.<br>
| | |
| Dla języka rozpoznawalnego <math>L</math> wprowadzimy pojęcie automatu minimalnego
| | |
| rozpoznającego <math>L</math> i prawej
| | <option><math>n\geq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option> |
| kongruencji syntaktycznej, która odgrywa istotną rolę w problemach zwiazanych
| | |
| z automatem minimalnym.
| | <option><math>n\leq 2^{\left\lceil \log_2 n \right\rceil}</math>,</option> |
| | |
| | <option><math>\left\lceil \log_2 \left\lceil n/2 \right\rceil \right\rceil=\left\lceil \log_2 \left( n/2 \right) \right\rceil</math>,</option> |
| | |
| | <option><math>\left\lfloor \log_2 \left\lceil n/2 \right\rceil \right\rfloor=\left\lfloor \log_2 \left( n/2 \right) \right\rfloor</math>.</option> |
| | </quiz> |
|
| |
|
| ; Słowa kluczowe
| |
| : wyrażenie regularne, prawa kongruencja syntaktyczna, kongruencja
| |
| syntaktyczna, monoid syntaktyczny, automat minimalny.
| |
|
| |
|
| ==Wyrażenia regularne==
| | <quiz> |
| | Dowolny niepusty podzbiór <math>S\subseteq \mathbb{N}</math> zbioru liczb naturalnych |
| | |
| | |
| | ma w sobie liczbę największą |
| | |
| | ma w sobie liczbę najmniejszą |
| | |
| | ma w sobie liczbę największą oraz liczbę najmniejszą |
| | |
| | ma w sobie liczbę najmniejszą ale nigdy nie ma największej |
| | </quiz> |
|
| |
|
| 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:
| |
|
| |
|
| # <math>\emptyset \in\mathcal{R} </math>, <math>\forall a \in A \;\;\; \{ a \} \in\mathcal{R} </math>
| | <quiz> |
| | Zbiór <math>S\subseteq\mathbb{N}</math> jest taki, że jeśli <math>s\in S</math> to <math>s+1\in S</math> . |
| | Jeśli <math>9\in S</math> , to: |
|
| |
|
| # jeśli <math>X, Y \in\mathcal{R} </math>, to <math>X \cup Y, \;\; X \cdot Y \;\; \in\mathcal{R} </math>
| | <math>S=\mathbb{N}</math> |
|
| |
|
| # jeśli <math> X \in\mathcal{R} </math>, to <math>X^* = \bigcup_{n=0} ^\infty X^n \in\mathcal{R} </math>
| | <math>S=\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math> |
|
| |
|
| Wprost z definicji wynika, że <math>\left\{ 1\right\} =\emptyset ^{*}\in \mathcal{R} </math> oraz
| | <math>S\subseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math> |
| ż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>
| | <math>S\supseteq\mathbb{N}-\left\lbrace 0,1,2,3,4,5,6,7,8 \right\rbrace</math> |
| | </quiz> |
|
| |
|
| Wprowadzona w ten sposób definicja rodziny języków regularnych wymaga
| |
| uzasadnienia faktu, iż definiowany obiekt, definiowana rodzina, istnieje. Zauważmy więc,
| |
| że warunki 1-3 definicji [[##defin:zbreg|Uzupelnic defin:zbreg|]] 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
| |
|
| |
|
| <center><math>\mathcal{REG}(A^{*})=\bigcap \mathcal{R},</math></center> | | <quiz> |
| | Zbiór <math>S\subseteq\mathbb{N}</math> jest taki, że jeśli <math>a,b\in S</math> , |
| | to <math>a+b\in S</math> oraz <math>a+b+1\not\in S</math> . |
| | Jeśli <math>0,2 \in S</math> , to: |
|
| |
|
| po wszystkich rodzinach <math>\mathcal{R} </math> spełniających warunki 1-3 definicji [[##defin:zbreg|Uzupelnic defin:zbreg|]].
| | <math>S=\mathbb{N}</math> |
|
| |
|
| Zauważmy, że w świetle powyższej definicji fakt, że <math>X \in\mathcal{REG}(A^{*}) </math> oznacza, że <math>X</math> można
| | zbiór <math>S</math> zawiera wszystkie liczby naturalne, które są parzyste |
| 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.
| |
|
| |
|
| Niech <math>A</math> będzie alfabetem, a zbiór <math>\{+ , \star , \emptyset , (,)\}</math>
| | zbiór <math>S</math> jest zawarty w zbiorze liczb naturalnych, które są parzyste |
| 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:
| |
|
| |
|
| # <math>{\bf \alpha} = \emptyset</math>
| | zbiór <math>S</math> jest zbiorem wszystkich liczb naturalnych, które są parzyste |
| # <math>{\bf \alpha} = a \in A \;\; ({\bf \alpha}</math> jest literą)
| | </quiz> |
|
| |
|
| # <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>.
| |
|
| |
|
| Przyjmujemy oznaczenia:
| | <quiz> |
| | Ostatnią cyfrą liczby <math>3^{3^n}</math> jest: |
|
| |
|
| <center><math>\emptyset ^{*}=1 \;\;\text{ oraz }\; \alpha ^{*}\alpha =\alpha ^{+}. </math></center>
| | zawsze <math>3</math> |
|
| |
|
| Rodzinę wyrażeń regularnych nad alfabetem <math>A</math> oznaczamy symbolem <math>\mathcal{WR} </math>.
| | zawsze <math>3</math> lub <math>7</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. | |
|
| |
|
| '''Wartościowaniem wyrażenia regularnego''' nazywamy
| | zawsze <math>7</math> |
| odwzorowanie
| |
|
| |
|
| <center><math>|\: \: |:\mathcal{WR}\longrightarrow \mathcal{P}(A^{*})</math></center>
| | jakakolwiek z cyfr <math>0,1,2,3,4,5,6,7,8,9</math> |
| | </quiz> |
|
| |
|
| określone następująco:
| |
|
| |
|
| # <math> \mid \emptyset \mid = \emptyset </math>
| | <quiz> |
| | Jeśli <math>Z \subseteq \mathbb{N}</math> jest jakimś zbiorem liczb naturalnych, |
| | który wraz z każdym początkowym fragmentem zbioru <math>\mathbb{N}</math> |
| | postaci <math>\left\lbrace 0,\ldots,k-1 \right\rbrace</math> zawiera również kolejną liczbę <math>k</math>, to wtedy |
|
| |
|
| # <math>\mid a \mid = \{ a \} </math>
| | zbiór <math>Z</math> zawiera wszystkie liczby naturalne poza skończonym podzbiorem |
|
| |
|
| # <math>\mid ({\bf \alpha} + {\bf \beta})\mid = \mid {\bf \alpha} \mid \cup \mid {\bf \beta} \mid</math> <br> <math> \mid ({\bf \alpha} {\bf \beta}) \mid = \mid {\bf \alpha} \mid \cdot \mid {\bf \beta} \mid </math><br> <math>\mid {\bf \alpha}^* \mid = \mid {\bf \alpha} \mid ^*</math>
| | zbiór <math>Z</math> zawiera wszystkie liczby naturalne |
|
| |
|
| Odwzorowanie określające wartość wyrażenia regularnego nie jest, jak można zauważyć,
| | zbiór <math>Z</math> zawiera nieskończenie wiele liczb naturalnych |
| 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.
| |
|
| |
|
| Wyrażenia regularne <math> {\bf \alpha} , {\bf \beta} </math> nazywamy '''równoważnymi''' i
| | zbiór <math>Z</math> jest pusty |
| oznaczamy <math>{\bf \alpha} = {\bf \beta} </math>, jeśli <math> \mid {\bf \alpha} \mid = \mid {\bf \beta} \mid </math>.
| | </quiz> |
|
| |
|
| Problem równoważności wyrażeń regularnych jest rozstrzygalny i jest PSPACE-zupełny.
| |
| Wrócimy do tego problemu w kolejnych wykładach.
| |
|
| |
|
| Oto przykłady równoważnych wyrażeń regularnych
| | <quiz> |
| | Grupa uczniów stojących przed klasą skłóciła się do tego stopnia, że nikt z nikim się nie lubił. Jeden z nich, aby naprawić relacje, wymyślił, że jeżeli wszyscy znajdujący się wewnątrz klasy będą pogodzeni, to nie powinno być problemu, aby któryś stojący na zewnątrz klasy wszedł do środka i pogodził się ze wszystkimi, będącymi w klasie. Drugi z nich zauważył jednak, że nic z tego nie wyjdzie, bo w środku nikogo nie ma. Czy klasa jest w stanie się pogodzić? |
|
| |
|
| <center><math>\aligned\alpha_1 + \alpha_2 & = & \alpha_2+ \alpha_1\\ (\alpha_1 + \alpha_2) +\alpha_3 & = & \alpha_1+ (\alpha_2 + \alpha_3) \\
| | klasa na pewno się nie pogodzi |
| (\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>
| |
|
| |
|
| gdzie <math>\alpha ,\alpha _{1},\alpha _{2},\alpha _{3}\in \mathcal{WR} </math>.
| | klasa się pogodzi, jeżeli każdy pójdzie za radą pierwszego ucznia |
|
| |
|
| { Wprost z definicji wyrażenia regularnego wynika następujaca równoważność:}
| | jeżeli w klasie byłaby już jedna osoba, to reszta klasy miałaby szansę się pogodzić |
|
| |
|
| {{fakt|[Uzupelnij]||
| | jeżeli w klasie byłyby już co najmniej dwie osoby, |
| <math>L\in \mathcal{REG}(A^{*}) \Longleftrightarrow L = \mid {\bf \alpha} \mid </math> dla pewnego <math>{\bf \alpha} \in\mathcal{WR} </math>.
| | przy czym osoby w klasie byłyby ze sobą pogodzone, |
| | to reszta klasy miałaby szansę się pogodzić |
| | </quiz> |
|
| |
|
| }}
| | |
| | | <quiz> |
| Wyrażenia regularne dają bardzo wygodne narzędzie zapisu języków należących do
| | Jeśli <math>S\subseteq\mathbb{N}</math> , to: |
| rodziny <math>\mathcal{REG}(A^{*})</math>.
| | |
| Np. język nad alfabetem
| | zbiór <math>S</math> ma element największy |
| <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>
| | zbiór <math>S</math> ma element najmniejszy |
| Z kolei wyrażenie regularne <math>a^+ b^+</math> oznacza język <math>L=\{a^nb^m : n,m\geq 1\}</math>.
| | |
| | | zbiór <math>S</math> ma element największy, o ile <math>S</math> jest niepusty |
| 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
| | zbiór <math>S</math> ma element najmniejszy, o ile <math>S</math> jest niepusty |
| będziemy zapisywać ten fakt jako <math>L= \alpha</math>. Będziemy zatem mówić w dalszym ciągu
| | </quiz> |
| 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.
| |
| | |
| ---- dla dociekliwych - start ----
| |
| | |
| 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 <math>1 </math>
| |
| 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.
| |
| | |
| ---- dla dociekliwych - end ----
| |
| | |
| ==Prawa kongruencja syntaktyczna i kongruencja syntaktyczna==
| |
| | |
| Opis języka regularnego za pomocą wyrażeń regularnych jest bardzo wygodny,
| |
| 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
| |
| dwie relacje:
| |
| | |
| # '''prawą kongruencję syntaktyczną''' <math>\; P_L^r , \;</math> przyjmując<br>
| |
| dla dowolnych słów <math>u, v \in A^* </math> {}<br>
| |
| <math>u \; P_L^r \; v \;\; \mbox{ wtedy i tylko wtedy, gdy
| |
| 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>
| |
| dla dowolnych <math>u, v \in A^* </math>{}<br>
| |
| <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
| |
| znaczy relacja <math>\; P_L^r , \;</math>
| |
| jest rzeczywiście prawą kongruencją, a <math>\; P_L , \;</math> kongruencją.
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Niech <math>A=\{ a,b\}</math> będzie alfabetem.
| |
| | |
| # Dla języka <math>L=a^+b^+ </math> relacja
| |
| | |
| ## <math>P_L^r</math> ma <math>4</math> klasy równoważności:
| |
| <math>\;\;L, \;\;A^*baA^*+b^+,\;\; a^+, \;\;1</math>
| |
| | |
| ## <math>P_L</math> ma <math>5</math> klas równoważności:
| |
| <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
| |
| | |
| ## dla <math>P_L^r</math> klasami równoważności są zbiory <br>
| |
| <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>
| |
| <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>
| |
| | |
| }}
| |
| | |
| Udowodnimy następujące własności relacji <math>\; P_L^r \;</math> oraz <math>\; P_L \;</math>.
| |
| | |
| Prawa kongruencja syntaktyczna <math>\; P_L^r \;</math> jest największą w sensie inkluzji spośród wszystkich
| |
| 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
| |
| 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>
| |
| | |
| W konsekwencji <math>\rho \subseteq P_L^r.</math> W
| |
| 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>.
| |
| 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 [[##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>
| |
| | |
| Jeśli język <math>L </math> jest regularny, to relacja <math>\; P_L^r \;</math> jest największą
| |
| 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 ----
| |
| | |
| Pojęcie, które wprowadzimy teraz - monoid syntaktyczny języka - wiąże teorię
| |
| języków formalnych, a
| |
| w szczególności teorię języków rozpoznawalnych, z 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'''
| |
| języka <math>\; L \;</math> nazywamy strukturę ilorazową
| |
| | |
| <center><math>M(L) = A^*/P_L .</math></center>
| |
| | |
| Dualnie, tworząc iloraz <math>S(L) = A^+/P_L</math> wprowadza się pojęcie półgrupy syntaktycznej
| |
| języka <math>\; L \;</math>. Oba wprowadzone tu pojęcia zilustrowane bedą w trakcie dalszych
| |
| rozważań.
| |
| | |
| ---- dla dociekliwych - end ----
| |
| | |
| ==AUTOMAT MINIMALNY==
| |
| | |
| Określenie języka rozpoznawalnego postuluje istnienie automatu o skończonej
| |
| 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>
| |
| 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
| |
| wykładzie przedstawimy algorytmy konstrukcji automatu minimalnego.
| |
| | |
| W poniższym twierdzeniu występuje automat ilorazowy </math>{A}_{P^{r}_{L}} <math>
| |
| określony przez
| |
| prawą kongruencję </math>P_L^r<math>.
| |
| | |
| \begintheor
| |
| | |
| Dla dowolnego automatu </math>{A} <center><math>= (S,A,f,s_0,T) \;</math> rozpoznającego
| |
| język <math>\; L \subset A^* \;</math> istnieje jedyny
| |
| epimorfizm <math>\varphi :\mathcal{A}\longrightarrow \mathcal{A}_{P^{r}_{L}} </math>
| |
| taki, że <math>\varphi (s_{0})=[1]_{P^{r}_{L}}. </math>
| |
| | |
| Prawa kongruencja automatowa <math>\sim _{\mathcal{A}} </math> ma
| |
| skończony indeks
| |
| i <math>L=\bigcup _{u\in L}[u]_{\sim _{\mathcal{A}}} </math>.
| |
| Zatem z twierdzenia [[##trr2|Uzupelnic trr2|]] wynika, że
| |
| | |
| <center><math>\sim _{\mathcal{A}}\subseteq P^{r}_{L}=\sim _{\mathcal{A}_{P^{r}_{L}}}.</math></center>
| |
| | |
| Istnienie epimorfizmu <math>\; \varphi \;</math> wynika z twierdzenia 1.1, wykład 3.
| |
| Epimorfizm ten określony jest dla dowolnego stanu <math>s\in S </math>
| |
| równością <math> \varphi(s) = f^*([1]_{P_L^r},w) = [w]_{P_L^r},</math> gdzie <math>w </math> jest
| |
| słowem takim, że <math>f(s_0,w)=s</math>.
| |
| | |
| Jest to jedyny epimorfizm spełniający warunki tezy dowodzonego
| |
| twierdzenia. Dla każdego epimorfizmu <math>\; \psi \;</math> takiego,
| |
| że <math>\psi :\mathcal{A}\longrightarrow \mathcal{A}_{P^{r}_{L}} </math>
| |
| i <math>\psi (s_{0})=[1]_{P^{r}_{L}} </math>
| |
| 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>
| |
| 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
| |
| formułujemy w następującym wniosku.
| |
| | |
| Niech <math>\; L \subset A^* \;</math> będzie dowolnym językiem. Automat
| |
| | |
| <center><math>\mathcal{A}_{P^{r}_{L}}=\left( A^{*}/_{P^{r}_{L}},A,f^{*},[1]_{P^{r}_{L}},T\right), </math></center>
| |
| | |
| gdzie <math>\; T = \{ [w]_{P_L^r} \; : \; w \in L \}, \;</math> jest automatem
| |
| minimalnym rozpoznającym język <math>\; L \;</math>. Oznaczać go
| |
| będziemy symbolem <math>\mathcal{A}_{L} </math>.
| |
| | |
| ---- dla dociekliwych - start ----
| |
| | |
| Następne twierdzenie charakteryzuje monoid przejść automatu minimalnego i
| |
| 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.{}{}
| |
| | |
| 1. Dla dowolnego języka <math>L\in \mathcal{REC}(A^{*}) </math> monoid przejść automatu minimalnego <math>\mathcal{A}_{L} </math> jest
| |
| izomorficzny z monoidem syntaktycznym <math> M(L) </math> języka <math>L</math>, czyli
| |
| | |
| <center><math>M(\mathcal{A}_{L})\sim M(L). </math></center>
| |
| | |
| {}{}
| |
| | |
| 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
| |
| | |
| <center><math>P_{L}=Ker_{\tau _{\mathcal{A}_{L}}}, </math></center>
| |
| | |
| gdzie zgodnie z definicją dla dowolnych <math>w,u\in A^{*} </math>
| |
| | |
| <center><math>\tau _{\mathcal{A}_{L}}(w)([u]_{P^{r}_{L}})=f^{*}([u]_{P^{r}_{L}},w)=[uw]_{P^{r}_{L}}.</math></center>
| |
| | |
| <center><math>\begin{array} {c}
| |
| (u,w)\in Ker_{\tau _{\mathcal{A}_{L}}}\Leftrightarrow \forall v\in A^*\;\;
| |
| \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>
| |
| | |
| Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku
| |
| ma postać: <br> | |
| | |
| RYSUNEK ja-lekcja4-w-rys1.pdf<br>
| |
| | |
| czyli <math>M(\mathcal{A}_{L})\sim M(L) </math>. <br>
| |
| 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 [[##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>
| |
| 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
| |
| równość
| |
| <center><math>\; L = k^{-1}(k(L)). \;</math></center> W tym celu wystarczy oczywiście udowodnić inkluzję
| |
| <math>\; k^{-1}(k(L)) \subseteq L</math>. <br>
| |
| | |
| <center><math>\begin{array} {c}
| |
| 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\\
| |
| \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>.
| |
| <math>\diamondsuit</math>
| |
| | |
| ---- dla dociekliwych - end ----
| |
| | |
| Z twierdzenia [[##3.1|Uzupelnic 3.1|]] wynika, że określenie klas abstrakcji prawej kongruencji syntaktycznej
| |
| <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ą
| |
| 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
| |
| | |
| <math>\rho_i = \{ (u,w) \in \; A^* \times A^* \; : \; (ua,wa) \in \; \rho_{i-1} \;\;\; \forall a \in A \cup \{1\}\}.</math>
| |
| | |
| { Wtedy <math>\;\; \bigcap \rho_i = P_L^r \;\;</math>. }
| |
| | |
| Na początku uzasadnimy, że <math>\; \bigcap \rho_i \;</math> jest prawą kongruencją na <math>\; A^*</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 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>
| |
| | |
| Dla uzasadnienia inkluzji <math>\bigcap \rho_i \;\subseteq\; P_L^r</math> zauważmy, że
| |
| jeśli <math>x \; \bigcap \rho_i \; y ,</math> to dla dowolnego <math>z\in A^{*} </math> mamy
| |
| <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>
| |
| 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
| |
| żą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>
| |
| | |
| Kolejne twierdzenie charakteryzuje relację <math>P^r_L</math> dla języka rozpoznawalnego i orzeka, iż
| |
| w przypadku języka rozpoznawalnego ciąg relacji <math>\rho_i</math>, aproksymujacych <math>P^r_L</math>, jest
| |
| 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:
| |
| | |
| # Język <math>L</math> jest rozpoznawalny
| |
| | |
| # Relacja <math>P^r_L</math> ma skończony indeks
| |
| | |
| # 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>
| |
| | |
| Dowód poprowadzimy według następujacego schematu:
| |
| | |
| { [[##u1|Uzupelnic u1|]] <math>\Longleftrightarrow </math> [[##u2|Uzupelnic u2|]]<math>\Longleftrightarrow </math>[[##u3|Uzupelnic u3|]] }
| |
| | |
| [[##u1|Uzupelnic u1|]] <math>\Longrightarrow </math> [[##u2|Uzupelnic u2|]]
| |
| | |
| { <math>P^r_L</math> jest największą w sensie inkluzji relacją spełniająca
| |
| warunki punktu 2 z twierdzenia 1.2, wykład 3. Z tego samego twierdzenia wynika
| |
| skończoność indeksu. }
| |
| | |
| [[##u1|Uzupelnic u1|]]<math>\Longleftarrow </math> [[##u2|Uzupelnic u2|]]
| |
| | |
| Relacja <math>P^r_L</math> jest prawą kongruencją, ma skończony indeks oraz
| |
| <center><math>L = \bigcup_{w \in L}[w]_{P^r_L}.</math></center> Z twierdzenia z 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|]]
| |
| | |
| Dowód poprowadzimy nie wprost. Załóżmy więc, że dla każdego <math>i\in {\Bbb N} </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 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.
| |
| | |
| [[##u2|Uzupelnic u2|]] <math>\Longleftarrow </math> [[##u3|Uzupelnic u3|]]
| |
| | |
| Udowodnimy indukcyjnie ze względu na <math>j</math>, że każda z relacji <math>\rho_j</math> dla <math>j=1,...,i</math>
| |
| 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>
| |
| | |
| Wykorzystamy powyżej udowodnione własności do konstrukcji automatu minimalnego rozpoznającego
| |
| 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]||
| |
| | |
| 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>.
| |
| Skonstruujemy minimalny automat akceptujący język <math>L</math>.
| |
| | |
| ; <math>\rho _{1}</math>
| |
| : <math>L=aA^* +A^* a,\;\; A^{*}\setminus L =bA^*b +b+1</math>
| |
| | |
| ; <math>\rho _{2}</math>
| |
| : <math>aA^*a+a,\;\; bA^*a, \;\; bA^*b +b+1,</math>
| |
| | |
| ; <math>\rho _{3}</math>
| |
| : <math>aA^*a+a,\;\; bA^*a, \;\; bA^*b +b, \;\;1,</math>
| |
| | |
| Ponieważ <math>\rho _{3}=\rho _{4}</math>, to <math>P^r_L=\rho _{3}</math> i automat minimalny ma <math>4</math> stany.<br>
| |
| 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
| |
| | |
| }}
| |
| | |
| {{cwiczenie|[Uzupelnij]||
| |
| | |
| Dla języka <math>L=\left\{ w \in \{ a,b\}^* :\#_a w =2k, \#_b w =2l+1
| |
| ,\; k,l\geq 0 \right\} </math> określimy ciąg relacji <math>{\rho}_i</math>, a
| |
| następnie relację <math>P^{r}_{L} </math>. Umożliwi nam to, w świetle
| |
| 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>
| |
| : <math>L, A^{*}\setminus L</math>
| |
| | |
| ; <math>\rho _{2}</math>
| |
| : <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>
| |
| automat minimalny <math>\mathcal{A}_{L}=\left( A^{*}/_{\rho _{2}},f^{*},s_{0},T\right) </math>
| |
| przedstawiony jest przy pomocy grafu:
| |
| | |
| RYSUNEK ja-lekcja4-w-rys3.JPG<br>
| |
| | |
| }}
| |
| | |
| ---- dla dociekliwych - start ----
| |
| | |
| Powyższe twierdzenia podają również sposób konstrukcji
| |
| monoidu syntaktycznego języka <math>L</math>.
| |
| | |
| ---- dla dociekliwych - end ----
| |
