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

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.

Twierdzenie Kleene

Stephen Cole Kleene (1909-1994)
Zobacz biografię

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

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 1

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)$, $: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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle f((s_1,S'_2),a) = \left\{ \begin{array} {ll} (f_1(s_1,a),f_2(S'_2,a)) & \text{gdy} f_1(s_1,a) \notin T_1 ,\\ (f_1(s_1,a),f_2(S'_2,a) \cup \{ {s_0}^2\}) & \text{gdy}f_1(s_1,a) \in T_1, \end{array} \right} .

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle f'(s,a) = \left\{ \begin{array} {ll} \{ f(s,a)\} & \text{gdy} f(s,a) \notin T ,\\ \{ f(s,a),s_0 \} & \text{gdy} f(s,a) \in T \end{array} \right} .

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 2

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 3

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 4

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)$,

$L(s,S_1,t)=\bar{L}(s,S_1\setminus \{s\},s{)}^{*}[\bigcup _{r\in S_1\setminus \{s\}}A(s,r)L(r,S_1-\{s\},t)]$.

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

Rysunek 5

$\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 6

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^{*})$.

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

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

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

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

2 Z twierdzenia Kleene'ego, punkt 4 i 5, wynika zamkniętość ze względu na katenację i operację iteracji $*$.

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

$L\in {ℛ}{ℰ}{𝒢}(A^{*})⟹:h(L)\in {ℛ}{ℰ}{𝒢}(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.

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

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

$L\in {ℛ}{ℰ}{𝒢}(B^{*})⟹:h^{-1}(L)\in {ℛ}{ℰ}{𝒢}(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 4 twierdzenia 1.2 z wykładu 3 (patrz twierdzenie 1.2. wykład 3), wnioskujemy, że $h^{-1}(L)\in {ℛ}{ℰ}{𝒢}(A^{*})$ .

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

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

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ż

$w\in L({𝒜}):⟺:s=f(s_0,w)\in T:⟺:s_o{\mapsto }^{*}ws,s\to 1\in P:⟺:w\in L(G)$.

Dla $w=1$ mamy $1\in L({𝒜}):⟺:s_0\to 1\in P:⟺: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

$P(v)=\{v\to x{v}^{″}:x\ne 1,\mathrm{\exists }{v}^{\prime }\in V_N(v),v^{\prime }\to x{v}^{″}\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

$L({𝒜})=\{w\in V_T^{*}:::f(s_0)\cap T\ne \mathrm{\varnothing }\}=L$.

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

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

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 7

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\}$.

2. 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 8

$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 2.3.

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 2.2. (patrz twierdzenie 2.2.) 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.

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.