Języki, automaty i obliczenia/Wykład 7: Twierdzenie Kleene'ego. Własności języków i gramatyk regularnych

Wprowadzenie

W wykładzie udowodnimy twierdzenie Kleene'ego, które orzeka, że

rodzina języków regularnych jest identyczna z rodziną języków rozpoznawanych przez automaty o skończonej liczbie stanów. Przedstawimy własności języków regularnych i gramatyk typu (3). Na koniec uzasadnimy, że rodziny języków regularnych, rozpoznawalnych oraz generowanych przez gramatyki typu (3), są tożsame.

Słowa kluczowe

twierdzenie Kleene, języki regularne, języki rozpoznawane, języki typu (3)

zamkniętość na działania, gramatyka typu (3), gramatyka prawoliniowa i lewoliniowa.

Twierdzenie Kleene

Wiemy już, z poprzednich wykładów, że rodzina wyrażeń regularnych określa rodzinę języków regularnych. Celem pierwszej części tego wykładu jest ustalenie związku pomiędzy rodziną języków regularnych a rodziną języków rozpoznawanych przez automaty o skończonej liczbie stanów. Twierdzenie, udowodnione przez S.C.Kleene'ego w roku 1956, orzeka, iż te dwie rodziny języków są identyczne.

Twierdzenie

Dla dowolnego skończonego alfabetu $A$

${ℛ}{ℰ}{𝒢}(A^{*})={ℛ}{ℰ}{𝒞}(A^{*})$

.

Dowód

Dowód pierwszej części twierdzenia, czyli inkluzja ${ℛ}{ℰ}{𝒢}(A^{*})\subseteq {ℛ}{ℰ}{𝒞}(A^{*})$ , będzie prowadzony zgodnie ze strukturą definicji rodziny języków regularnych ${ℛ}{ℰ}{𝒢}(A^{*})$ .

1. Język pusty $\mathrm{\varnothing }$ jest rozpoznawany przez dowolny automat ${𝒜}=(S,A,f,s_0,T),$ w którym zbiór stanów końcowych $T$ jest pusty.

2. Język a złożony z dowolnej litery $a\in A$ jest rozpoznawany przez automat

RYSUNEK ja-lekcja7-w-rys1

Dla dalszej części dowodu ustalmy, iż dane są języki $L_1,L_2$ rozpoznawane odpowiednio przez automaty deterministyczne ${{𝒜}}_i=(S_i,f_i,{s_0}^i,T_i)$, gdzie $i=1,2.$

3. Sumę mnogościową języków $L_1,L_2$, czyli język $L=L_1\cup L_2$ rozpoznaje automat ${𝒜}=(S,f,s_0,T)$, dla którego $S=S_1\times S_2$, $s_0=({s_0}^1,{s_0}^2)$, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \: \displaystyle T = T_1 \times S_2\; \cup \;S_1 \times T_2} oraz dla dowolnego stanu $(s_1,s_2)\in S$ i litery $a\in A$ funkcja przejść określona jest równością

$f((s_1,s_2),a)=(f_1(s_1,a),f_2(s_2,a)).$

4. Katenację języków $L_1,L_2$, czyli język $L=L_1\cdot L_2$ rozpoznaje automat ${𝒜}=(S,f,s_0,T)$, dla którego $S=S_1\times {𝒫}(S_2),s_0=(s_0^1,\mathrm{\varnothing })$ oraz dla dowolnego stanu $(s_1,S{\text{'}}_2)\in S$ i litery $a\in A$ funkcja przejść określona jest następująco:

$f((s_1,S{\text{'}}_2),a)=\{\begin{array}{ll}(f_1(s_1,a),f_2(S{\text{'}}_2,a))& \text{<mrow data-mjx-texclass="ORD">gdy</mrow>}{f}_1(s_1,a)\notin T_1,\\ (f_1(s_1,a),f_2(S{\text{'}}_2,a)\cup \{{s_0}^2\})& \text{<mrow data-mjx-texclass="ORD">gdy</mrow>}{f}_1(s_1,a)\in T_1,{\displaystyle }\end{array}$

a zbiorem stanów końcowych jest

$T=S_1\times \{S^{\prime }\in {𝒫}(S_2):S^{\prime }\cap T_2\ne \mathrm{\varnothing }\}.$

5. Załóżmy, że język $L$ rozpoznaje automat ${𝒜}=(S,f,s_0,T)$. Określimy automat niedeterministyczny, który będzie rozpoznawał gwiazdkę Kleene języka $L$, czyli $L^{*}.$ Automat niedeterministyczny ${{𝒜}}^{\prime }=(S,f^{\prime },\{s_0\},T)$, w którym

$f^{\prime }(s,a)=\{\begin{array}{ll}\{f(s,a)\}& \text{<mrow data-mjx-texclass="ORD">gdy</mrow>}f(s,a)\notin T,\\ \{f(s,a),s_0\}& \text{<mrow data-mjx-texclass="ORD">gdy</mrow>}f(s,a)\in T{\displaystyle }\end{array}$

rozpoznaje język język $L^{+}.$ Dowód tego faktu jest indukcyjny i pozostawiamy go na ćwiczenia. Zauważmy teraz, że język $\{1\}$ rozpoznaje automat

RYSUNEK ja-lekcja7-w-rys2

Ponieważ $L^{*}=L^{+}\cup \left\{1\right\}$ , to korzystając z udowodnionej już zamkniętości języków rozpoznawanych ze względu na sumę mnogościową, stwierdzamy, że istnieje automat rozpoznający język $L^{*}$.

Zatem dowód inkluzji ${ℛ}{ℰ}{𝒢}(A^{*})\subseteq {ℛ}{ℰ}{𝒞}(A^{*})$ jest zakończony.

{ Przejdziemy teraz do dowodu inkluzji ${ℛ}{ℰ}{𝒢}(A^{*})\supseteq {ℛ}{ℰ}C(A^{*})$ . }

Niech $L$ oznacza dowolny język rozpoznawany przez automat ${𝒜}=(S,f,s_0,T).$ Dowód polega na rozbiciu języka $L$ na fragmenty, dla których stwierdzenie, że są to języki regularne będzie dość oczywiste. Natomiast sam język $L$ będzie wynikiem operacji regularnych określonych na tych właśnie fragmentach. Poniżej przeprowadzamy defragmentację języka $L.$

Dla $s,t\in S$ niech

$L(s,t)=\{w\in A^{*}:f(s,w)=t\}.$

Jest to język złożony ze słów, które przeprowadzają stan $s$ automatu ${𝒜}$ w stan $t$ . Ogół liter alfabetu $A$ przeprowadzających stan $s$ w $t$ oznaczymy przez

$A(s,t)=\{a\in A:f(s,a)=t\}.$

Dla stanów $s,t\in S$ i zbioru $S_1\subseteq S$ niech

$L(s,S_1,t)=\{w\in A^{*}:f(s,w)=t,f(s,w_1)\in S_1:w=w_{1}v,w_1,v\in A^{*}\}.$

Jest to język, który można przedstawić graficznie następująco:

RYSUNEK ja-lekcja7-w-rys3

Na koniec przyjmijmy $\bar{L}(s,S_2,t)=\{w\in A^{*}:f(s,w)=t,f(s,w_1)\in S_2:w=w_{1}v,w_1,v\in A^{+}\},$

określony dla $S_2\subseteq S$ i $s,t\in S-S_2$

Język ten jest graficznie interpretowany poniżej.

RYSUNEK ja-lekcja7-w-rys4

Wprost z określeń wynika, że wszystkie wprowadzone powyżej języki są regularne, czyli należą do rodziny ${ℛ}{ℰ}{𝒢}(A^{*})$ . Dowód tego faktu przebiega indukcyjnie ze względu na liczbę elementów zbiorów $S_1$ i $S_2$. Szczegóły tego dowodu pominiemy. Natomiast warto wskazać rolę, jaką spełniają w dowodzie wprowadzone wyżej języki. A mianowicie:

$L(s,\left\{s\right\},s)=A(s,s{)}^{*}$

,

$\bar{L}(s,\left\{r\right\},t)=A(s,r)A(r,r{)}^{*}A(r,t)$

,

Parser nie mógł rozpoznać (nieznana funkcja „\Large”): {\displaystyle \displaystyle L(s,S_1,t) = \overline{L}(s,S_1 \setminus \{s\},s)^*\; {\Large [}\bigcup_{r \in S_1 \setminus \{s\}}A(s,r)L(r,S_1 - \{s\},t)\;{\Large ]}.}

Tę ostatnią równość przedstawia poniższy rysunek.

RYSUNEK ja-lekcja7-w-rys5

$\bar{L}(s,S_2,t)=\bigcup _{r,r^{\prime }\in S_2}A(s,r)L(r,S_2,r^{\prime })A(r^{\prime },t),$

co graficznie można przedstawić następująco:

RYSUNEK ja-lekcja7-w-rys6

Dochodzimy więc do konkluzji, iż jezyki $L(s,S_1,t)$ oraz $\bar{L}(s,S_2,t)$ są regularne. W szczególności zatem regularny jest język $L(s_0,S,t)=L(s_0,t)$.

Język $L$ możemy przedstawić w następującej postaci:

$L=\bigcup _{t\in T}\{w\in A^{*}:f(s_0,w)=t\}=\bigcup _{t\in T}L(s_0,t),$

co w połączeniu z ustaleniami punktu 3 z poprzedniej części dowodu uzasadnia tezę, że

język $L$ należy do rodziny ${ℛ}{ℰ}{𝒢}(A^{*}).\mathrm{♢}$

Własności języków regularnych i gramatyk regularnych

W tej części wykładu omówimy własności rodziny języków i gramatyk regularnych, czyli typu (3) w hierarchii Chomsky'ego. Ustalimy też związek pomiędzy językami a gramatykami regularnymi. Zbadamy zamkniętość rodziny języków regularnych ze względu na operacje mnogościowe, czyli ze względu na sumę, przecięcie, różnicę i uzupełnienie. Rozpoczniemy jednak tę część wykładu od wprowadzenia jednoargumentowego działania na słowach zwanego odbiciem zwierciadlanym.

Definicja

Odbiciem zwierciadlanym słowa $w=a_1\dots a_n\in A^{*}$ nazywamy słowo $\overleftarrow{w}=a_n\dots a_1$. Odbiciem zwierciadlanym języka $L\subset A^{*}$ nazywamy język $\overleftarrow{L}=\{\overleftarrow{w}\in A^{*}:w\in L\}.$

Twierdzenie

Rodzina ${ℛ}{ℰ}{𝒢}(A^{*})={ℛ}{ℰ}{𝒞}(A^{*})$ jest zamknięta ze względu na:

1. sumę mnogościową, przecięcie, różnicę i uzupełnienie,
2. katenację i operację iteracji `{} $*$ `{},
3. obraz homomorficzny,
4. podstawienie regularne,
5. przeciwobraz homomorficzny,
6. odbicie zwierciadlane.

Dowód

{}

Uzupelnic uw:bool|. Zamkniętość rodziny języków ${ℛ}{ℰ}{𝒢}(A^{*})$ ze względu na sumę mnogościową wynika z twierdzenia Kleene'ego. Automat akceptujący iloczyn języków otrzymujemy, zmieniając odpowiednio zbiór stanów końcowych w automacie rozpoznającym sumę. Bowiem pozostając przy oznaczeniach punktu 3 z dowodu twierdzenia Kleene'ego, automat ${𝒜}=(S,f,s_0,F),$ gdzie $F=T_1\times T_2$, rozpoznaje język $L_1\cap L_2.$ Jeśli automat ${𝒜}=(S,f,s_0,T)$ akceptuje język $L$, to automat $\overline{{𝒜}}=(S,f,s_0,S\mathrm{\setminus }T)$ akceptuje język $\bar{L}=A^{*}\setminus L.$ Ostatnia własność implikuje zamkniętość ze względu na uzupełnienie.

Uzupelnic uw:kat|. Z twierdzenia Kleene'ego, punkt 4 i 5, wynika zamkniętość ze względu na katenację i operację iteracji `{} $*$ `{}.

Uzupelnic uw:hom|. Niech $h:A^{*}⟶B^{*}$ będzie homomorfizmem. Dowód implikacji

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L\in \mathcal{REG}(A^{*})\Longrightarrow \: h(L)\in \mathcal{REG}(B^{*})}

przeprowadzimy zgodnie ze strukturą definicji rodziny języków regularnych. Dla $L=\mathrm{\varnothing }$ i dla $L=\{a\}$ , gdzie $a$ jest dowolną literą alfabetu $A$ , implikacja jest oczywista. W pierwszym przypadku obrazem homomorficznym jest język pusty, a w drugim język $\{w\}$ , gdzie $w$ jest pewnym słowem nad alfabetem $B$ . Dla dowolnych języków regularnych $X,Y\in {ℛ}{ℰ}{𝒢}(A^{*})$ prawdziwe są równości:

• $h(X\cup Y)=h(X)\cup h(Y)\in {ℛ}{ℰ}{𝒢}(B^{*})$ ,
• $h(X\cdot Y)=h(X)\cdot h(Y)\in {ℛ}{ℰ}{𝒢}(B^{*})$ ,
• $h(X^{*})=h(\bigcup _{n=0}^{\mathrm{\infty }}{X}^n)=\bigcup _{n=0}^{\mathrm{\infty }}(h(X){)}^n=(h(X){)}^{*}\in {ℛ}{ℰ}{𝒢}(B^{*}),$

co kończy dowód tego punktu.

Uzupelnic uw:podst|. Uzasadnienie jest podobne jak dla homomorfizmu. Jedyna różnica tkwi w tym, że dla podstawienia regularnego $s:A^{*}⟶{𝒫}(B^{*})$ i dla dowolnej litery $a\in A$ wartość podstawienia na literze jest pewnym językiem regularnym $s(a)=L\in {ℛ}{ℰ}{𝒢}(B^{*})$ , a nie słowem jak w przypadku homomorfizmu.

Uzupelnic uw:przec|. Niech $h:A^{*}⟶B^{*}$ będzie homomorfizmem. Aby udowodnić implikację

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L\in \mathcal{REG}(B^{*})\Longrightarrow \: h^{-1}(L)\in \mathcal{REG}(A^{*})}

, odwołamy się do własności, że dla języka $L\in {ℛ}{ℰ}{𝒢}(B^{*})$ istnieje skończony monoid $M$ i homomorfizm $\phi :B^{*}⟶M$ taki, że $L={\phi }^{-1}(\phi (L)).$ Dla homomorfizmu $\phi \circ h:A^{*}⟶M$ mamy

równość: $((\phi \circ h{)}^{-1}\circ (\phi \circ h))(h^{-1}(L))=h^{-1}(L).$

Korzystając teraz z punktu Uzupelnic 4| twierdzenia Uzupelnic ja-lekcja3-w tw2.1|, wnioskujemy, że $h^{-1}(L)\in {ℛ}{ℰ}{𝒢}(A^{*})$ .

Uzupelnic uw:odb|. Wykorzystamy tutaj zapis języka regularnego przez wyrażenie regularne. Niech dla języka $L\in {ℛ}{ℰ}{𝒢}(A^{*})$ wyrażenie regularne $\alpha \in {𝒲}{ℛ}$ będzie takie, że $L=\mid \mathit{\alpha }\mid$. Wtedy język $\overleftarrow{L}$ jest opisany przez wyrażenie regularne $\overleftarrow{\mathit{\alpha }}$, które uzyskujemy z $\mathit{\alpha }$ przez odbicie zwierciadlane, a dokładniej odwrócenie kolejności katenacji w każdej sekwencji tego działania występującej w wyrażeniu regularnym.

$\mathrm{♢}$

W wykładzie drugim wprowadziliśmy pojęcie gramatyki. Wracamy do tego pojęcia, a w szczególności do gramatyki typu (3), czyli regularnej. Przypomnijmy, że produkcje takiej gramatyki $G=(V_N,V_T,v_0,P)$ mają postać:

$v\to v^{\prime }xlubv\to x,$

gdzie $v,v^{\prime }\in V_N,x\in {V_T}^{*}$. Gramatykę typu (3), nazywamy inaczej lewostronną lub lewoliniową. Określa się też gramatykę regularną prawostronną (prawoliniową). Jest to gramatyka $G=(V_N,V_T,v_0,P)$, której produkcje są postaci:

$v\to x{v}^{\prime }lubv\to x,$

gdzie $v,v^{\prime }\in V_N,x\in {V_T}^{*}$. Jeśli język $L=L(G)$ jest generowany przez gramatykę typu (3) (lewoliniową), to jego odbiciem zwierciadlanym jest $\overleftarrow{L}=L(\overleftarrow{G})$, gdzie $\overleftarrow{G}$ jest gramatyką prawoliniową, którą uzyskuje się z gramatyki $G$ przez odbicie zwierciadlane prawych stron produkcji. Oznacza to, iż zmieniamy produkcje według następujących zasad:

$v\to v^{\prime }x$ zastępujemy przez $v\to \overleftarrow{x}{v}^{\prime },$ $v\to x$ zastępujemy przez $v\to \overleftarrow{x}.$

Oczywiście, jeśli $L$ jest językiem generowanym przez gramatykę prawoliniową, to $\overleftarrow{L}$ jest generowany przez odpowiednią gramatykę lewoliniową.

Podamy teraz charakterystykę rodziny języków regularnych ${ℛ}{ℰ}{𝒢}(A^{*})$ przez rodzinę gramatyk prawoliniowych.

Twierdzenie

Niech $L\subset A^{*}$. Język $L\in {ℛ}{ℰ}{𝒢}(A^{*})$ wtedy i tylko wtedy, gdy $L=L(G)$ dla pewnej gramatyki prawoliniowej $G$.

Dowód

Załóżmy, że automat ${𝒜}=(S,A,f,s_0,T)$ rozpoznaje język $L$ . Definiujemy gramatykę $G=(V_N,V_T,v_0,P)$ przyjmując $V_N=S,V_T=A,v_0=s_0$ oraz określając w następujący sposób zbiór produkcji

$P=\{s\to af(s,a):s\in S,a\in A\}\cup \{s\to 1:s\in T\}.$

Dla dowolnego stanu $s\in S$ i słowa $w\in A^{+}$ prawdziwa jest równoważność

$s_0{\mapsto }^{*}ws⟺f(s_0,w)=s.$

Dowód przeprowadzimy indukcyjnie ze względu na długość słowa $w$. Niech $w=a,$ dla pewnego $a\in A$. Z definicji zbioru produkcji $P$ wynika równoważność

$s_0\to as⟺s=f(s_0,a).$

Rozważmy teraz $w=a_1\dots a_n$ oraz $s_0{\mapsto }^{*}ws$. Z założenia indukcyjnego

wynika, że $f(s_0,a_1\dots a_{n-1})=s^{\prime }⟺s_0{\mapsto }^{*}{a}_1\dots a_{n-1}{s}^{\prime }$

oraz, że $s=f(s^{\prime },a_n)$ wtedy i tylko wtedy, gdy $s^{\prime }\mapsto a_{n}s.$ A więc fakt, że $s=f(s_0,w)=f(s_0,a_1\dots a_n)=f(f(s_0,a_1\dots a_{n-1}),a_n)$ jest równoważny temu, że $s^{\prime }=f(s_0,a_1\dots a_{n-1})\mapsto a_{n}s$ . A to z kolei równoważne jest

$s_0{\mapsto }^{*}{a}_1\dots a_{n-1}{s}^{\prime },s^{\prime }\mapsto a_{n}s$

i ostatecznie równoważne faktowi, że $s_0{\mapsto }^{*}{a}_1\dots a_{n-1}{a}_{n}s$ . A zatem dowodzona równoważność jest prawdziwa dla $w\in A^{+}$, ponieważ

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle w\in L(\mathcal{A})\: \Longleftrightarrow \: s=f(s_{0},w)\in T\: \Longleftrightarrow \: s_{o}\mapsto ^{*}ws,\, s\rightarrow 1\in P\: \Longleftrightarrow \: w\in L(G).}

Dla $w=1$ mamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle 1\in L(\mathcal{A})\: \Longleftrightarrow \: s_{0}\rightarrow 1\in P\: \Longleftrightarrow \: 1\in L(G), } co kończy dowód w jedną stronę.

Rozważmy teraz język $L=L(G)$ generowany przez pewna gramatykę prawoliniową $G=(V_N,V_T,v_0,P)$. Skonstruujemy gramatykę równoważną $G$ i taką, w której wszystkie produkcje są postaci $v\to a{v}^{\prime }$ lub $v\to 1$, gdzie $v,v^{\prime }\in V_N,a\in A$. Będziemy zamieniać produkcje występujące w gramatyce $G$ na inne, o żądanej postaci, zgodnie z następująmi zasadami:

1. Produkcje typu $v\to v^{\prime }$, gdzie $v,v^{\prime }\in V_N$

Z symbolem nieterminalnym $v\in V_N$ kojarzymy określony poniżej zbiór

$V_N(v)=\{v^{\prime }\in V_N:v\to v_1\to \dots \to v_n\to v^{\prime }wG\}$

oraz zbiór produkcji

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle P(v) = \{ v \rightarrow xv" \; : \; x \neq 1 , \; \exists v' \in V_N(v) , v' \rightarrow xv" \in P \} \cup} $\cup \{v\to x:\mathrm{\exists }{v}^{\prime }\in V_N(v),v^{\prime }\to x\in P\}.$

Dla każdego takiego symbolu $v\in V_N$ usuwamy ze zbioru $P$ wszystkie produkcje $v\to v^{\prime }$ i wprowadzamy na to miejsce wszystkie produkcje ze zbioru $P(v)$.

2. Produkcje typu $v\to x$ dla $x\ne 1$.

Jeśli produkcja taka występuje w $P$ i $x\ne 1$, to do alfabetu nieterminalnego $V_N$ dodajemy nowy symbol $v_x$. Następnie ze zbioru $P$ usuwamy powyższą produkcję i dodajemy dwie nowe:

$v\to x{v}_x,v_x\to 1.$

Zauważmy, że jeśli $x\ne y$, to $v_x\ne v_y$.

3. Produkcje typu $v\to x{v}^{\prime }$ dla $\mid x\mid >1.$

Jeśli $v\to a_1\dots a_n{v}^{\prime }\in P$, przy czym $n\ge 2$, to do alfabetu nieterminalnego $V_N$ dodajemy nowe symbole $v_1,\dots v_n$, produkcję $v\to a_1\dots a_n{v}^{\prime }$ usuwamy ze zbioru $P$ i

dodajemy produkcje: $v\to a_1{v}_1,v_1\to a_2{v}_2,\dots ,v_{n-1}\to a_n{v}^{\prime }.$

Po opisanych powyżej trzech modyfikacjach gramatyki $G$ generowany język, co łatwo zauważyć, nie ulega zmianie. Zatem skonstruowana gramatyka jest równoważna wyjściowej. Dla otrzymanej gramatyki określamy teraz automat niedeterministyczny ${𝒜}=(S,A,f,\{s_0\},T)$, przyjmując $S=V_N$, $A=V_T$ oraz $s_0=v_0$ i definiując następująco funkcję przejść: $f(v,a)=\{v^{\prime }\in V_N:v\to a{v}^{\prime }\in P\}.$ Przjmując $T=\{v\in V_N:v\to 1\in P\}$ jako zbiór stanów końcowych, stwierdzamy, że automat ${𝒜}$ rozpoznaje język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathcal{A})=\{w\in V_{T}^{*}\: :\: f(s_{0})\cap T\neq \emptyset \}=L. }

Uzyskany rezultat, w świetle równości ${ℛ}{ℰ}{𝒢}(A^{*})={ℛ}{ℰ}C(A^{*})$ , kończy dowód twierdzenia.

$\mathrm{♢}$

Algorytmiczną stroną równoważności udowodnionej w powyższym twierdzeniu zajmiemy się w następnym wykładzie. Przykłady ilustrujące twierdzenie zamieszczamy poniżej.

Przykład

1. Niech ${𝒜}=(S,A,f,s_0,T)$ będzie automatem takim, że
   

$S=\{s_0,s_1,s_2\},A=\{a,b\},T=\{s_1\}$, a graf przejść wygląda następująco:

RYSUNEK ja-lekcja7-w-rys7

Gramatyka $G=(S,A,s_0,P)$, gdzie

$P=\{s_0\to a{s}_1,s_0\to b{s}_2,s_1\to a{s}_2,s_1\to b{s}_0,s_1\to 1,s_2\to a{s}_0,s_2\to b{s}_1\}$

akceptuje język $L({𝒜})$.

Zauważmy, że język $L({𝒜})=L(G)=\{w\in A^{*}:{\mathrm{\#}}_{a}w-{\mathrm{\#}}_{b}w=1mod3\}.$

1. Niech $G=(\{v_0,v_1\},\{a,b\},v_0,P)$, gdzie

$P=\{v_0\to a{v}_0,v_0\to ab,v_0\to b{v}_1,v_1\to 1\}.$

Gramatykę $G$ przekształcamy w równoważną gramatykę

$G^{\prime }=(\{v_0,v_1,v_2,v_b\},\{a,b\},v_0,P^{\prime }),$

gdzie

$P^{\prime }=\{v_0\to a{v}_0,v_0\to a{v}_2,v_0\to b{v}_1,v_2\to b{v}_b,v_1\to 1,v_b\to 1\}.$

Niedeterministyczny automat ${{𝒜}}_{ND}=(\{v_0,v_1,v_2,v_b\},\{a,b\},f,v_0,\{v_1,v_b\})$, gdzie graf przejśc wygląda następująco:

RYSUNEK ja-lekcja7-w-rys8

$L(G)=L({{𝒜}}_{ND})=a^{*}b$

Wykorzystując udowodnione do tej pory własności rodziny języków generowanych przez gramatyki regularne, uzasadnimy teraz, iż ta właśnie rodzina, czyli ogół języków typu (3) w hierarchii Chomsky'ego pokrywa się z rodziną ${ℛ}{ℰ}{𝒢}(A^{*})$ .

Twierdzenie

Dla dowolnego alfabetu $A$ rodziny języków regularnych $A^{*}$ oraz języków generowanych przez gramatyki regularne są równe, czyli ${ℛ}{ℰ}{𝒢}(A^{*})={{ℒ}}_3$ .

Dowód

Odbicie zwierciadlane dowolnego języka $L\in {ℛ}{ℰ}{𝒢}(A^{*})$ , czyli język $\overleftarrow{L}$ należy również do rodziny ${ℛ}{ℰ}{𝒢}(A^{*})$ , co oznacza, że $\overleftarrow{L}\in {ℛ}{ℰ}C(A^{*})$ . Na podstawie twierdzenia Uzupelnic twprawlin| istnieje więc gramatyka prawoliniowa $G$ taka, że $\overleftarrow{L}=L(G)$ . A stąd wniosek, że $L=\overleftarrow{\overleftarrow{L}}=L(\bar{G})$ dla pewnej gramatyki $\bar{G}$ typu (3). Zatem $L\in {{ℒ}}_3$ .

Rozważmy teraz język $L$ typu (3), czyli $L=L(G)$ dla pewnej gramatyki regularnej. A więc $\overleftarrow{L}=L(\bar{G})$ dla pewnej gramatyki prawoliniowej i $\overleftarrow{L}\in {ℛ}{ℰ}C(A^{*})$ . Z twierdzenia Kleene'ego wynika, że $\overleftarrow{L}\in {ℛ}{ℰ}{𝒢}(A^{*})$ i ostatecznie $L=\overleftarrow{\overleftarrow{L}}\in {ℛ}{ℰ}{𝒢}(A^{*})$ , co kończy dowód twierdzenia.

$\mathrm{♢}$

Zamkniemy rozważania następującą konkluzją podsumowującą główne rezultaty tego wykładu.

Dla dowolnego skończonego alfabetu $A$ prawdziwe są równości:

${ℛ}{ℰ}{𝒢}(A^{*})={ℛ}{ℰ}{𝒞}(A^{*})={{ℒ}}_3$

, czyli wprowadzone pojęcia rodziny języków regularnych, rozpoznawalnych oraz generowanych przez gramatyki typu (3) są tożsame.