Test GR3

Wyrażenia regularne

Definicja 1.1

Niech $A$ będzie skończonym alfabetem. Rodzina ${ℛ}{ℰ}{𝒢}(A^{*})$ języków regularnych nad alfabetem $A$ to najmniejsza, w sensie inkluzji, rodzina ${ℛ}$ języków zawartych w $A^{*}$ taka, że:

(1) $\mathrm{\varnothing }\in {ℛ}$, $\mathrm{\forall }a\in A\{a\}\in {ℛ}$

(2) jeśli $X,Y\in {ℛ}$, to $X\cup Y,X\cdot Y\in {ℛ}$

(3) jeśli $X\in {ℛ}$, to $X^{*}=\bigcup _{n=0}^{\mathrm{\infty }}{X}^n\in {ℛ}$

Wprost z definicji wynika, że $\left\{1\right\}={\mathrm{\varnothing }}^{*}\in {ℛ}$ oraz że dla dowolnego języka regularnego zachodzi równość $X\in {ℛ}$ jest

$X^{+}=\bigcup _{n=1}^{\mathrm{\infty }}{X}^n=X\cdot X^{*}\in {ℛ}.$

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 1.1 spełnia na przykład rodzina ${𝒫}(A^{*})$ wszystkich podzbiorów $A^{*}$, a zatem klasa takich rodzin nie jest pusta. Ponadto łatwo możemy stwierdzić, że jeśli rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathcal{R}_{1},\: \mathcal{R}_{2} } spełniają warunki 1-3 powyższej definicji, to rodzina ${{ℛ}}_1\cap {{ℛ}}_2$ również spełnia te warunki. Stąd możemy wyprowadzić wniosek, że najmniejsza rodzina spełniającą te warunki, to przecięcie

${ℛ}{ℰ}{𝒢}(A^{*})=\bigcap {ℛ},$

po wszystkich rodzinach ${ℛ}$ spełniających warunki 1-3 definicji 1.1. Zauważmy, że w świetle powyższej definicji fakt, że $X\in {ℛ}{ℰ}{𝒢}(A^{*})$ oznacza, że $X$ można uzyskać z liter alfabetu i zbioru pustego $\mathrm{\varnothing }$ 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 ${ℛ}{ℰ}{𝒢}(A^{*})$. Ta obserwacja prowadzi do pojęcia wyrażeń regularnych, formalnego zapisu języków regularnych.

Definicja 1.2

Niech $A$ będzie alfabetem, a zbiór $\{+,\star ,\mathrm{\varnothing },(,)\}$ alfabetem rozłącznym z $A$. Słowo $\mathit{\alpha }\in \mathbf{(}A\cup \{+,\star ,\mathrm{\varnothing },(,)\}{\mathbf{)}}^{*}$ jest wyrażeniem regularnym nad alfabetem $A$ wtedy i tylko wtedy, jeśli:

(1) $\mathit{\alpha }=\mathrm{\varnothing }$

(2) $\mathit{\alpha }=a\in A(\mathit{\alpha }$ jest literą)

(3) $\mathit{\alpha }$ jest w postaci $(\mathit{\beta }+\mathit{\gamma }),(\mathit{\beta }\mathit{\gamma }),{\mathit{\gamma }}^{*}$, gdzie $\mathit{\beta },\mathit{\gamma }$są wyrażeniami regularnymi nad alfabetem $A$.

Przyjmujemy oznaczenia:

${\mathrm{\varnothing }}^{*}=1\text{ oraz }{\alpha }^{*}\alpha ={\alpha }^{+}.$

Rodzinę wyrażeń regularnych nad alfabetem $A$ oznaczamy symbolem ${𝒲}{ℛ}$. Łatwo zauważyć związek pomiędzy wyrażeniami regularnymi oraz wprowadzoną wcześniej rodziną ${ℛ}{ℰ}{𝒢}(A^{*})$, regularnych języków wolnego monoidu $A^{*}$. Związek ten ustala poniższa definicja. Definicja 1.3

Wartościowaniem wyrażenia regularnego nazywamy odwzorowanie

Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\: \: |:\mathcal{WR}\longrightarrow \mathcal{P}(A^{*})}

określone następująco:

(1) $\mid \mathrm{\varnothing }\mid =\mathrm{\varnothing }$

(2) $\mid a\mid =\{a\}$

(3) $\mid (\mathit{\alpha }+\mathit{\beta })\mid =\mid \mathit{\alpha }\mid \cup \mid \mathit{\beta }\mid$

           $\mid (\mathit{\alpha }\mathit{\beta })\mid =\mid \mathit{\alpha }\mid \cdot \mid \mathit{\beta }\mid$

           $\mid {\mathit{\alpha }}^{*}\mid =\mid \mathit{\alpha }{\mid }^{*}$

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 $a^{*}$ oraz $(a^{*}{)}^{*}$. Zwróćmy uwagę na wartość wyrażenia regularnego oznaczonego symbolem $1$.

Jest mianowicie

$\mid 1\mid =\mid {\mathrm{\varnothing }}^{*}\mid =\mid \mathrm{\varnothing }{\mid }^{*}={\mathrm{\varnothing }}^{*}=\{1\}$

Wprowadza się następującą relację równoważności w rodzinie wyrażeń regularnych.

Definicja 1.4

Wyrażenia regularne $\mathit{\alpha },\mathit{\beta }$ nazywamy równoważnymi i oznaczamy $\mathit{\alpha }=\mathit{\beta }$, jeśli $\mid \mathit{\alpha }\mid =\mid \mathit{\beta }\mid$.

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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}

gdzie $\alpha ,{\alpha }_1,{\alpha }_2,{\alpha }_3\in {𝒲}{ℛ}$.

Wprost z definicji wyrażenia regularnego wynika następujaca równoważność:

Fakt 1.1

$L\in {ℛ}{ℰ}{𝒢}(A^{*})⟺L=\mid \mathit{\alpha }\mid$ dla pewnego $\mathit{\alpha }\in {𝒲}{ℛ}$.

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

Zauważmy na koniec rozważań o wyrażeniach regularnych, że dość prosty w zapisie język $L=\{a^n{b}^n:n\ge 1\}$ nie należy do rodziny ${ℛ}{ℰ}{𝒢}(A^{*})$ i nie można go zapisać przy pomocy wyrażeń regularnych.

Uwaga [Dla dociekliwych]

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 $\alpha ,{\alpha }_1,{\alpha }_2\in {𝒲}{ℛ}$ głębokość zagnieżdżenia gwiazdki definiuje się jako liczbę $sh(\alpha )$ równą $0$, gdy $\alpha$ jest literą z alfabetu lub zbiorem pustym, równą $max\{i,j\},$ gdy $\alpha ={\alpha }_1\cup {\alpha }_2$ lub $\alpha ={\alpha }_1\cdot {\alpha }_2$ i $sh({\alpha }_1)=i$, $sh({\alpha }_2)=j$ oraz równą $i+1$ dla $\alpha =({\alpha }_1{)}^{*}$. Głębokość zagnieżdżenia gwiazdki dla języka regularnego $L$ określa się jako najmniejszą liczbę $sh(L)=sh(\alpha )$, gdzie $\alpha$ jest wyrażeniem regularnym reprezentującym język $L$. 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 $L$. 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 $k\in \mathbb{\mathbb{N}}$ można wskazać język regularny $L$ taki, że $sh(L)=k$. 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.

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 $L\subset A^{*}$ będzie dowolnym językiem. W monoidzie $A^{*}$ wprowadzamy następujące dwie relacje:

1. prawą kongruencję syntaktyczną $P_L^r,$ przyjmując
   

dla dowolnych słów $u,v\in A^{*}$ {}

Parser nie mógł rozpoznać (błąd składni): {\displaystyle u \; P_L^r \; v \;\; \mbox{ wtedy i tylko wtedy, gdy spełniony jest warunek}}

$\mathrm{\forall }w\in A^{*}uw\in L\iff vw\in L,$

1. kongruencję syntaktyczną $P_L,$ przyjmując
   

dla dowolnych $u,v\in A^{*}${}

$u{P}_{L}v\text{ wtedy i tylko wtedy, gdy spełniony jest warunek}$ $\mathrm{\forall }{w}_1,w_2\in A^{*}{w}_{1}u{w}_2\in L\iff w_{1}v{w}_2\in L.$

Łatwo stwierdzić, że nazwy wprowadzonych relacji pokrywają się z ich własnościami, to znaczy relacja $P_L^r,$ jest rzeczywiście prawą kongruencją, a $P_L,$ kongruencją.

Ćwiczenie [Uzupelnij]

Niech $A=\{a,b\}$ będzie alfabetem.

1. Dla języka $L=a^{+}{b}^{+}$ relacja

1. 1. $P_L^r$ ma $4$ klasy równoważności:

$L,A^{*}ba{A}^{*}+b^{+},a^{+},1$

1. 1. $P_L$ ma $5$ klas równoważności:

$L,A^{*}ba{A}^{*},b^{+},a^{+},1$

1. Dla języka $L=\{a^n{b}^n:n\ge 1\}$ obie relacje mają nieskończony indeks

1. 1. dla $P_L^r$ klasami równoważności są zbiory
      

$L_i=\{a^n{b}^{n-i}:n\ge i,n\ge 1\}$ dla $i\in {\mathbb{\mathbb{N}}}_0$, $A^{*}\setminus \bigcup _{i=0}^{\mathrm{\infty }}{L}_i$

1. 1. dla $P_L$ klasami równoważności są zbiory
      

$L_i=\{a^n{b}^{n-i}:n\ge i,n\ge 1\}$ dla $i\in {\mathbb{\mathbb{N}}}_0$,
$L{\text{'}}_i=\{a^{n-i}{b}^n:n\ge i,n\ge 1\}$ dla $i\in \mathbb{\mathbb{N}}$
$A^{*}\setminus [\bigcup _{i=1}^{\mathrm{\infty }}(L_i\cup L{\text{'}}_i)\cup L_0]$

Udowodnimy następujące własności relacji $P_L^r$ oraz $P_L$.

Prawa kongruencja syntaktyczna $P_L^r$ jest największą w sensie inkluzji spośród wszystkich

prawych kongruencji

$\rho$

takich, że

$L=\bigcup _{w\in L}[w{]}_{\rho }$

Kongruencja syntaktyczna $P_L$ jest największą w sensie inkluzji spośród wszystkich

kongruencji

$\rho$

takich, że

$L=\bigcup _{w\in L}[w{]}_{\rho }$

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

$uw\rho vw\Rightarrow (uw\in L\iff vw\in L)\iff u{P}_L^{r}v.$

W konsekwencji $\rho \subseteq P_L^r.$ W szczególności więc dla dowolnego $u\in A^{*}$ ma miejsce inkluzja $[u{]}_{\rho }\subseteq [u{]}_{P_L^r}.$ Zatem $L\subset \bigcup _{w\in L}[w{]}_{P_L^r}$. Aby udowodnić inkluzję w stronę przeciwną ustalmy dowolne $u\in L$ i niech $v\in [u{]}_{P_L^r}.$ Przyjmując $w=1$ w definicji Uzupelnic d1| relacji $P_L^r$ otrzymamy równoważność $u\in L\iff v\in L.$ A więc $v\in L.$

$\mathrm{♢}$

Jeśli język $L$ jest regularny, to relacja $P_L^r$ jest największą w sensie inkluzji spośród wszystkich prawych kongruencji takich, że język $L$ jest sumą jej pewnych klas równoważnosci a relacja $P_L$ 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 $A^{*}$ 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 $L\subset A^{*}$ będzie dowolnym językiem. Monoidem syntaktycznym języka $L$ nazywamy strukturę ilorazową

$M(L)=A^{*}/P_L.$

Dualnie, tworząc iloraz $S(L)=A^{+}/P_L$ wprowadza się pojęcie półgrupy syntaktycznej języka $L$. 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

${𝒜}$

= (S,A,f,s_0,T) Parser nie mógł rozpoznać (błąd składni): {\displaystyle rozpoznający język } LParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } L. Parser nie mógł rozpoznać (nieznana funkcja „\enddefin”): {\displaystyle \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 } {A}_{P^{r}_{L}} Parser nie mógł rozpoznać (błąd składni): {\displaystyle określony przez prawą kongruencję } P_L^rParser nie mógł rozpoznać (nieznana funkcja „\begintheor”): {\displaystyle . \begintheor Dla dowolnego automatu } {A}

$=(S,A,f,s_0,T)$ rozpoznającego

język $L\subset A^{*}$ istnieje jedyny epimorfizm $\phi :{𝒜}⟶{{𝒜}}_{P_L^r}$ taki, że $\phi (s_0)=[1{]}_{P_L^r}.$

Prawa kongruencja automatowa ${\sim }_{{𝒜}}$ ma skończony indeks i $L=\bigcup _{u\in L}[u{]}_{{\sim }_{{𝒜}}}$. Zatem z twierdzenia Uzupelnic trr2| wynika, że

${\sim }_{{𝒜}}\subseteq P_L^r={\sim }_{{{𝒜}}_{P_L^r}}.$

Istnienie epimorfizmu $\phi$ wynika z twierdzenia 1.1, wykład 3. Epimorfizm ten określony jest dla dowolnego stanu $s\in S$ równością $\phi (s)=f^{*}([1{]}_{P_L^r},w)=[w{]}_{P_L^r},$ gdzie $w$ jest słowem takim, że $f(s_0,w)=s$.

Jest to jedyny epimorfizm spełniający warunki tezy dowodzonego twierdzenia. Dla każdego epimorfizmu $\psi$ takiego, że $\psi :{𝒜}⟶{{𝒜}}_{P_L^r}$ i $\psi (s_0)=[1{]}_{P_L^r}$

mamy
$\mathrm{\forall }s\in S$ $\psi (s)=\psi (f(s_o,w))=f^{*}(\psi (s_0),w)=f^{*}([1{]}_{P_L^r},w)=[w{]}_{P_L^r},$

gdzie $f(s_0,w)=s.$ Tak więc $\psi =\phi .\mathrm{♢}$

Zatem udowodnione twierdzenie zapewnia nas o istnieniu automatu minimalnego, co formułujemy w następującym wniosku.

Niech $L\subset A^{*}$ będzie dowolnym językiem. Automat

${{𝒜}}_{P_L^r}=(A^{*}{/}_{P_L^r},A,f^{*},[1{]}_{P_L^r},T),$

gdzie $T=\{[w{]}_{P_L^r}:w\in L\},$ jest automatem minimalnym rozpoznającym język $L$. Oznaczać go będziemy symbolem ${{𝒜}}_L$.

---

dla dociekliwych - start ----

Następne twierdzenie charakteryzuje monoid przejść automatu minimalnego i podaje kolejny warunek równoważny na to, żeby język $L$ był rozpoznawany przez automat.

Niech $L\subset A^{*}$ będzie dowolnym językiem.{}{}

1. Dla dowolnego języka $L\in {ℛ}{ℰ}{𝒞}(A^{*})$ monoid przejść automatu minimalnego ${{𝒜}}_L$ jest izomorficzny z monoidem syntaktycznym $M(L)$ języka $L$, czyli

$M({{𝒜}}_L)\sim M(L).$

{}{}

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

Dla dowodu punktu 1, wykażemy, że

$P_L=Ke{r}_{{\tau }_{{{𝒜}}_L}},$

gdzie zgodnie z definicją dla dowolnych $w,u\in A^{*}$

${\tau }_{{{𝒜}}_L}(w)([u{]}_{P_L^r})=f^{*}([u{]}_{P_L^r},w)=[uw{]}_{P_L^r}.$ $\begin{array}{c}(u,w)\in Ke{r}_{{\tau }_{{{𝒜}}_L}}\iff \mathrm{\forall }v\in A^{*}{\tau }_{{{𝒜}}_L}(u)([v{]}_{P_L^r})={\tau }_{{{𝒜}}_L}(w)([v{]}_{P_L^r})\iff [vu{]}_{P_L^r}=[vw{]}_{P_L^r}\iff \\ \iff \mathrm{\forall }v,z\in A^{*}vuz\in L\iff vwz\in L\iff [u{]}_{P_L}=[w{]}_{P_L}\iff (u,v)\in P_L\\ \end{array}$

Korzystamy teraz z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ma postać:

RYSUNEK ja-lekcja4-w-rys1.pdf

czyli $M({{𝒜}}_L)\sim M(L)$.
Dla dowodu punktu 2 załóżmy, że język $L$ jest rozpoznawalny. Zatem

$L=\bigcup _{w\in L}[w{]}_{\rho },$ gdzie $\rho$ jest kongruencją o skończonym indeksie.

Z twierdzenia Uzupelnic trr2| wnioskujemy, że $\rho \subseteq P_L.$ Oznacza to, że indeks relacji $P_L$ jest niewiększy od indeksu $\rho ,$ a co za tym idzie, $M(L)=A^{*}/P_L$ jest monoidem skończonym.

Dla dowodu implikacji w stronę przeciwną rozważmy epimorfizm kanoniczny $k:A^{*}⟶A^{*}/P_L=M(L).$

Pokażemy, że spełnia on warunki z punktu 4 twierdzenia 1.2 z wykładu 3. $M(L)$ jest skończony, więc pozostaje do wykazania równość

$L=k^{-1}(k(L)).$ W tym celu wystarczy oczywiście udowodnić inkluzję

$k^{-1}(k(L))\subseteq L$.

$\begin{array}{c}v\in k^{-1}(k(L))\Rightarrow k(v)\in k(L)\Rightarrow \mathrm{\exists }u\in L:k(v)=k(u)\in k(L)\iff \\ \iff \mathrm{\exists }u\in L:[v{]}_{P_L}=[u{]}_{P_L}\iff \mathrm{\exists }u\in L:v\in L\iff u\in L.\\ \end{array}$

Czyli $v\in L$ i $L=k^{-1}(k(L))$. $\mathrm{♢}$

---

dla dociekliwych - end ----

Z twierdzenia Uzupelnic 3.1| wynika, że określenie klas abstrakcji prawej kongruencji syntaktycznej $P_L^r$ prowadzi do określenia minimalnego automatu rozpoznającego język $L$. Prezentowane poniżej twierdzenia wskazują sposób konstrukcji prawej kongruencji syntaktycznej dla języka $L$.

Niech $L\subset A^{*}$ będzie dowolnym językiem,
a ${\mathrm{\Theta }}_L\subset A^{*}\times A^{*}$ relacją równoważności o dwóch klasach równoważności $L$ i $A^{*}\setminus L$. Przez ${\rho }_i$ dla $i\in \mathbb{\mathbb{N}}$ oznaczmy zstępujący ciąg relacji określony następująco:

${\rho }_1={\mathrm{\Theta }}_L,$ a dla $i=2,...$ przyjmijmy

${\rho }_i=\{(u,w)\in A^{*}\times A^{*}:(ua,wa)\in {\rho }_{i-1}\mathrm{\forall }a\in A\cup \{1\}\}.$

{ Wtedy $\bigcap {\rho }_i=P_L^r$. }

Na początku uzasadnimy, że $\bigcap {\rho }_i$ jest prawą kongruencją na $A^{*}$. Załóżmy więc, że słowa $x,y\in A^{*}$ są w relacji $x\bigcap {\rho }_{i}y$. Wybierzmy dowolne słowo $z\in A^{*}$ i niech $k$ oznacza długość tego słowa. Z założenia wynika, iż $x{\rho }_{i+k}y$, co w świetle definicji ciągu relacji ${\rho }_i$ implikuje, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle xz\: \rho _{i}\: yz. } Ponieważ $i$ jest dowolne wnioskujemy ostatecznie, że $xz\bigcap {\rho }_{i}yz,$ co kończy dowód faktu, że $\bigcap {\rho }_i$ jest prawą kongruencją.

Dowiedziemy teraz równości $\bigcap {\rho }_i=P_L^r.$

Dla uzasadnienia inkluzji $\bigcap {\rho }_i\subseteq P_L^r$ zauważmy, że jeśli $x\bigcap {\rho }_{i}y,$ to dla dowolnego $z\in A^{*}$ mamy $xz\bigcap {\rho }_{i}yz$, a w szczególności $xz{\rho }_{1}yz.$ Z definicji relacji ${\rho }_1$ dla dowolnego $z\in A^{*}$ prawdziwa

jest równoważność $xz\in L\iff yz\in L.$

A więc $x{P}_L^{r}y$. Inkluzję w stronę przeciwną pokażemy, dowodząc indukcyjnie ze względu na $i=1,2,...$ , że dla dowolnych $x,y\in A^{*}$ prawdziwa jest następująca implikacja

$x{P}_L^{r}y⟹x{\rho }_{i}y.$

Załóżmy zatem, że $x{P}_L^{r}y.$ Z definicji $P_L^r$ wynika, że dla dowolnego $z\in A^{*}$ prawdziwa jest równoważność

$xz\in L\iff yz\in L.$ Przyjmując $z=1$ otrzymujemy

żądaną własność dla ${\rho }_1.$ Załóżmy teraz, że prawdziwa jest implikacja

$x{P}_L^{r}y⟹x{\rho }_{i}y.$

dla $i=1,...,n-1$ oraz dla dowolnych $x,y\in A^{*}.$ Stąd, że $P_L^r$ jest prawą kongruencją, wnioskujemy, że dla dowolnego $a\in A\cup \{1\}$ spełniona jest relacja $xa{P}_L^{r}ya.$ Korzystając z założenia indukcyjnego mamy $xa{\rho }_{n-1}ya$ dla dowolnego $a\in A\cup \{1\}$. A to oznacza z definicji ${\rho }_i$, że $x{\rho }_{n}y$ i kończy dowód.

$\mathrm{♢}$

Kolejne twierdzenie charakteryzuje relację $P_L^r$ dla języka rozpoznawalnego i orzeka, iż w przypadku języka rozpoznawalnego ciąg relacji ${\rho }_i$, aproksymujacych $P_L^r$, 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:

1. Język $L$ jest rozpoznawalny

1. Relacja $P_L^r$ ma skończony indeks

1. Ciąg relacji ${\rho }_i$ stabilizuje się, co oznacza, że istnieje $i\in \mathbb{\mathbb{N}}$ takie, że ${\rho }_i={\rho }_{i+1}=....$Dla najmniejszego takiego $i$ prawdziwa jest równość ${\rho }_i=P_L^r.$

Dowód poprowadzimy według następujacego schematu:

{ Uzupelnic u1| $⟺$ Uzupelnic u2|$⟺$Uzupelnic u3| }

Uzupelnic u1| $⟹$ Uzupelnic u2|

{ $P_L^r$ 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. }

Uzupelnic u1|$⟸$ Uzupelnic u2|

Relacja $P_L^r$ jest prawą kongruencją, ma skończony indeks oraz

$L=\bigcup _{w\in L}[w{]}_{P_L^r}.$ Z twierdzenia z twierdzenia 1.2, wykład 3 wynika więc, że język $L$ jest rozpoznawalny.

Uzupelnic u2|$⟹$ Uzupelnic u3|

Dowód poprowadzimy nie wprost. Załóżmy więc, że dla każdego $i\in \mathbb{\mathbb{N}}$ jest ${\rho }_i\ne {\rho }_{i+1}.$ Oznacza to, że dla każdego $i\in \mathbb{\mathbb{N}}$ indeksy relacji ${\rho }_i$ tworzą ciąg silnie rosnący, to znaczy spełniają zależność $ind{\rho }_i<ind{\rho }_{i+1}.$ Ponieważ $ind{\rho }_1=2,$ to dla każdego $i\in \mathbb{\mathbb{N}}$ prawdziwa jest nierówność $ind{\rho }_i>i.$ A to prowadzi do wniosku, że dla dowolnego $i\in \mathbb{\mathbb{N}}$

$ind{P}_L^r=ind\bigcap {\rho }_i>i.$ Zatem indeks relacji $P_L^r$ jest nieskończony, co jest sprzeczne z założeniem.

Uzupelnic u2| $⟸$ Uzupelnic u3|

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

$\mathrm{♢}$

Wykorzystamy powyżej udowodnione własności do konstrukcji automatu minimalnego rozpoznającego język $L$. Warto zauważyc, iż punktem wyjścia dla tej konstrukcji jest język $L$ zadany, na przykład, poprzez wyrażenie regularne.

Ćwiczenie [Uzupelnij]

Niech do języka $L$ należą wszystkie słowa nad alfabetem $A=\{a,b{\}}^{*}$ zaczynające się lub kończące literą $a$. Skonstruujemy minimalny automat akceptujący język $L$.

${\rho }_1$

$L=a{A}^{*}+A^{*}a,A^{*}\setminus L=b{A}^{*}b+b+1$

${\rho }_2$

$a{A}^{*}a+a,b{A}^{*}a,b{A}^{*}b+b+1,$

${\rho }_3$

$a{A}^{*}a+a,b{A}^{*}a,b{A}^{*}b+b,1,$

Ponieważ ${\rho }_3={\rho }_4$, to $P_L^r={\rho }_3$ i automat minimalny ma $4$ stany.
Przyjmujemy $s_0=[1]$, $s_1=b{A}^{*}a$, $s_2=a{A}^{*}a+a$, $s_3=b{A}^{*}b+b$ oraz $T=\{s_1,s_2\}$, a automat minimalny ${{𝒜}}_L=(A^{*}{/}_{{\rho }_3},f^{*},s_0,T)$ przedstawiony jest przy pomocy grafu:

RYSUNEK ja-lekcja4-w-rys2.JPG

Ćwiczenie [Uzupelnij]

Dla języka $L=\{w\in \{a,b{\}}^{*}:{\mathrm{\#}}_{a}w=2k,{\mathrm{\#}}_{b}w=2l+1,k,l\ge 0\}$ określimy ciąg relacji ${\rho }_i$, a następnie relację $P_L^r$. 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 ${\rho }_1$ oraz ${\rho }_2$, ${\rho }_3={\rho }_2$, co kończy proces obliczania relacji ${\rho }_i$ i daje równość ${\rho }_2=P_L^r$.

${\rho }_1$

$L,A^{*}\setminus L$

${\rho }_2$

$L,L_1,L_2,L_3$, gdzie

$L_1=\{w\in \{a,b{\}}^{*}:{\mathrm{\#}}_{a}w=2k,{\mathrm{\#}}_{b}w=2l,k,l\ge 0\},$
$L_2\{w\in \{a,b{\}}^{*}:{\mathrm{\#}}_{a}w=2k+1,{\mathrm{\#}}_{b}w=2l+1,k,l\ge 0\},$
$L_3=\{w\in \{a,b{\}}^{*}:{\mathrm{\#}}_{a}w=2k+1,{\mathrm{\#}}_{b}w=2l,k,l\ge 0\},$

Przyjmując $s_0=L_1=[1]$, $s_1=L_3$, $s_2=L_2$, $s_3=L$ oraz $T=\{s_3\}$ automat minimalny ${{𝒜}}_L=(A^{*}{/}_{{\rho }_2},f^{*},s_0,T)$ przedstawiony jest przy pomocy grafu:

RYSUNEK ja-lekcja4-w-rys3.JPG

---

dla dociekliwych - start ----

Powyższe twierdzenia podają również sposób konstrukcji monoidu syntaktycznego języka $L$.

---

dla dociekliwych - end ----