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

From Studia Informatyczne

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.

Spis treści

Twierdzenie Kleene

Stephen Cole Kleene (1909-1994)Zobacz biografię
Enlarge
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 \displaystyle A

\displaystyle \mathcal{REG}(A^{*})=\mathcal{REC}(A^{*})

Dowód

Dowód pierwszej części twierdzenia, czyli inkluzja \displaystyle \mathcal{REG}(A^{*})\subseteq \mathcal{REC}(A^{*}) , będzie prowadzony zgodnie ze strukturą definicji rodziny języków regularnych \displaystyle \mathcal{REG}(A^{*}) .

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

2. Język a złożony z dowolnej litery \displaystyle a \in A jest rozpoznawany przez automat image:End_of_proof.gif



Rysunek 1

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

3. Sumę mnogościową języków \displaystyle L_1, L_2, czyli język \displaystyle L = L_1 \cup L_2 rozpoznaje automat \displaystyle \mathcal{A}  \displaystyle = (S,f,{s_0},T), dla którego \displaystyle S = S_1 \times S_2, \displaystyle s_0 =  ({s_0}^1,{s_0}^2), \displaystyle \:   \displaystyle T = T_1 \times S_2\; \cup \;S_1 \times  T_2 oraz dla dowolnego stanu \displaystyle (s_{1},s_{2})\in S i litery \displaystyle a\in A funkcja przejść określona jest równością

\displaystyle f((s_{1},s_{2}),a)=(f_{1}(s_{1},a),f_{2}(s_{2},a)).

4. Katenację języków \displaystyle L_1, L_2, czyli język \displaystyle L = L_1 \cdot L_2 rozpoznaje automat \displaystyle \mathcal{A}  \displaystyle = (S,f,{s_0},T), dla którego \displaystyle S=S_{1}\times \mathcal{P}(S_{2}),\quad s_{0}=\left(  s_{0}^{1},\emptyset \right) oraz dla dowolnego stanu \displaystyle (s_1,S'_2)  \in S i litery \displaystyle a\in A funkcja przejść określona jest następująco:

\displaystyle f((s_1,S'_2),a) = \left\{ \begin{array} {ll} (f_1(s_1,a),f_2(S'_2,a)) &  \textrm{gdy} \displaystyle f_1(s_1,a) \notin T_1\displaystyle  ,\\ (f_1(s_1,a),f_2(S'_2,a) \cup \{ {s_0}^2\}) &  \textrm{gdy}\displaystyle f_1(s_1,a) \in T_1, \displaystyle   \end{array}  \right.

a zbiorem stanów końcowych jest

\displaystyle T=S_{1}\times \left\{ S'\in \mathcal{P}(S_{2})\, :\, S'\cap T_{2}\neq \emptyset \right\} .

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

\displaystyle f'(s,a) = \left\{ \begin{array} {ll} \{ f(s,a)\} &  \textrm{gdy} \displaystyle f(s,a) \notin T\displaystyle  ,\\ \{ f(s,a),s_0 \} &  \textrm{gdy} \displaystyle f(s,a) \in T\displaystyle   \end{array}  \right.

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



Rysunek 2

Ponieważ \displaystyle 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 \displaystyle L^*.

Zatem dowód inkluzji \displaystyle \mathcal{REG}(A^{*})\subseteq \mathcal{REC}(A^{*}) jest zakończony.

Przejdziemy teraz do dowodu inkluzji \displaystyle \mathcal{REG}(A^{*})\supseteq \mathcal{RE}C(A^{*}) .

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

Dla \displaystyle s,t \in S niech

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

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

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

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

\displaystyle L(s,S_1,t) = \{ w \in A^* : f(s,w) =t, f(s,w_1) \in S_1\;:\;w= w_1v,\; w_1, v \in A^* \}.

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



Rysunek 3

Na koniec przyjmijmy
\displaystyle \overline{L}(s,S_2,t) = \{ w \in A^* : f(s,w)  =t, f(s,w_1) \in S_2\; : \;w = w_1v,\; w_1,v \in A^+ \},

określony dla \displaystyle  S_2 \subseteq S i \displaystyle 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 \displaystyle \mathcal{REG}(A^{*}) . Dowód tego faktu przebiega indukcyjnie ze względu na liczbę elementów zbiorów \displaystyle S_1 i \displaystyle S_2. Szczegóły tego dowodu pominiemy. Natomiast warto wskazać rolę, jaką spełniają w dowodzie wprowadzone wyżej języki. A mianowicie:

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


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


\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 5

\displaystyle \overline{L}(s,S_2,t) = \bigcup_{r,r' \in S_2} A(s,r) L(r,S_2,r') A(r',t),

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



Rysunek 6

Dochodzimy więc do konkluzji, iż jezyki \displaystyle L(s,S_{1},t) oraz \displaystyle \overline{L}(s,S_{2},t) są regularne. W szczególności zatem regularny jest język \displaystyle L(s_{0},S,t)=L(s_{0},t).

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

\displaystyle 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 \displaystyle L należy do rodziny \displaystyle \mathcal{REG}(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 \displaystyle  w = a_1 \ldots a_n \in A^* nazywamy słowo \displaystyle  \stackrel{\leftarrow}{w} = a_n \ldots a_1. Odbiciem zwierciadlanym języka \displaystyle L \subset A^* nazywamy język \displaystyle  \stackrel{\leftarrow}{L} = \{ \stackrel{\leftarrow}{w} \in A^* \; : \; w \in L \}.

Twierdzenie 2.1.

Rodzina \displaystyle \mathcal{REG}(A^{*})=\mathcal{REC}(A^{*}) jest zamknięta ze względu na:

(1) sumę mnogościową, przecięcie, różnicę i uzupełnienie,
(2) katenację i operację iteracji \displaystyle "*" ,
(3) obraz homomorficzny,
(4) podstawienie regularne,
(5) przeciwobraz homomorficzny,
(6) odbicie zwierciadlane.

Dowód

1. Zamkniętość rodziny języków \displaystyle \mathcal{REG}(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 \displaystyle \mathcal{A}  \displaystyle =(S,f,{s_0},F), gdzie \displaystyle F = T_1 \times T_2, rozpoznaje język \displaystyle L_1 \cap L_2. Jeśli automat \displaystyle \mathcal{A} \displaystyle =(S,f,s_0,T) akceptuje język \displaystyle L, to automat \displaystyle \overline{\mathcal{A}}  \displaystyle =(S,f,s_0,S\backslash T) akceptuje język \displaystyle \overline{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 \displaystyle "*".

3. Niech \displaystyle h: A^* \longrightarrow B^* będzie homomorfizmem. Dowód implikacji

\displaystyle L\in \mathcal{REG}(A^{*})\Longrightarrow \: h(L)\in \mathcal{REG}(B^{*})

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

  • \displaystyle h( X \cup Y)=h(X) \cup h(Y) \in\displaystyle \mathcal{REG}(B^{*}) ,
  • \displaystyle h( X \cdot Y) = h(X) \cdot h(Y) \in\displaystyle \mathcal{REG}(B^{*}) ,
  • \displaystyle {\displaystyle h(X^*)=h( \bigcup_{n=0} ^\infty X^n) = \bigcup_{n=0} ^\infty (h(X))^n = (h(X))^* \in}\displaystyle \mathcal{REG}(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 \displaystyle s:A^{*}\longrightarrow \mathcal{P}(B^{*}) i dla dowolnej litery \displaystyle a \in A wartość podstawienia na literze jest pewnym językiem regularnym \displaystyle s(a)=L\in \mathcal{REG}(B^{*}) , a nie słowem jak w przypadku homomorfizmu.

5. Niech \displaystyle h: A^* \longrightarrow B^* będzie homomorfizmem. Aby udowodnić implikację

\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 \displaystyle L  \in\displaystyle \mathcal{REG}(B^{*}) istnieje skończony monoid \displaystyle \; M \; i homomorfizm \displaystyle \varphi : B^* \longrightarrow M taki, że \displaystyle L = \varphi^{-1}(\varphi (L)). Dla

homomorfizmu \displaystyle  \varphi \circ h : A^* \longrightarrow M mamy równość:
\displaystyle  ((\varphi \circ h)^{-1} \circ (\varphi \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 \displaystyle  h^{-1}(L) \in\displaystyle \mathcal{REG}(A^{*}) .

6. Wykorzystamy tutaj zapis języka regularnego przez wyrażenie regularne. Niech dla języka \displaystyle L \in\displaystyle \mathcal{REG}(A^{*}) wyrażenie regularne \displaystyle \alpha \in \mathcal{WR} będzie takie, że \displaystyle  L = \mid {\bf \alpha} \mid. Wtedy język \displaystyle \stackrel{\leftarrow}{L} jest opisany przez wyrażenie regularne \displaystyle \stackrel{\leftarrow}{\bf \alpha}, które uzyskujemy z \displaystyle {\bf \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.

image:End_of_proof.gif

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 \displaystyle G=(V_N ,V_T ,v_0 ,P ) mają postać:

\displaystyle  v \rightarrow v' x \;\; lub \;\;\; v \rightarrow x,

gdzie \displaystyle v,v' \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 \displaystyle G=(V_N ,V_T ,v _0 ,P), której produkcje są postaci:

\displaystyle  v \rightarrow xv' \;\; lub \;\;\; v \rightarrow x,

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

\displaystyle  v \rightarrow v' x \;\; zastępujemy przez \displaystyle   \;\;\; v \rightarrow \stackrel{\leftarrow}{x}v',
\displaystyle  v \rightarrow x \;\; zastępujemy przez \displaystyle   \;\;\; v \rightarrow \stackrel{\leftarrow}{x}.

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

Podamy teraz charakterystykę rodziny języków regularnych \displaystyle \mathcal{REG}(A^{*}) przez rodzinę gramatyk prawoliniowych.

Twierdzenie 2.2.

Niech \displaystyle L \subset A^*. Język \displaystyle L \in\displaystyle \mathcal{REG}(A^{*}) wtedy i tylko wtedy, gdy \displaystyle L =L(G) dla pewnej gramatyki prawoliniowej \displaystyle G.

Dowód

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

\displaystyle P = \{ s \rightarrow a f(s ,a) \; :s \in S, a \in A \} \cup \{ s \rightarrow 1 \; : s \in T \} .

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

\displaystyle  s_0 \mapsto^* ws \;\; \Longleftrightarrow \;\; f(s_0 ,w) = s.

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

\displaystyle s_0 \rightarrow as \; \Longleftrightarrow \; s = f(s_0 ,a).

Rozważmy teraz \displaystyle w = a_1 \ldots a_n oraz \displaystyle s_0 \mapsto^* ws. Z założenia indukcyjnego

wynika, że
\displaystyle  f(s_0 , a_1 \ldots a_{n-1}) =s' \Longleftrightarrow s_0 \mapsto^* a_1 \ldots a_{n-1}s'

oraz, że \displaystyle  s = f(s' ,a_n ) wtedy i tylko wtedy, gdy \displaystyle s' \mapsto a_n s . A więc fakt, że \displaystyle s=f(s_{0},w)=f(s_{0},a_{1}\ldots a_{n})=f(f(s_{0},a_{1}\ldots a_{n-1}),a_{n}) jest równoważny temu, że \displaystyle s'=f(s_{0},a_{1}\ldots a_{n-1})\mapsto a_{n}s . A to z kolei równoważne jest

\displaystyle s_{0}\mapsto^{*}a_{1}\ldots a_{n-1}s',\;\;\;s'\mapsto a_{n}s

i ostatecznie równoważne faktowi, że \displaystyle s_{0}\mapsto ^{*}a_{1}\ldots a_{n-1}a_{n}s . A zatem dowodzona równoważność jest prawdziwa dla \displaystyle w \in A^+, ponieważ

\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 \displaystyle w=1 mamy \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 \displaystyle L = L(G) generowany przez pewna gramatykę prawoliniową \displaystyle G = (V_N , V_T , v_0 ,P). Skonstruujemy gramatykę równoważną \displaystyle G i taką, w której wszystkie produkcje są postaci \displaystyle v \rightarrow a v' lub \displaystyle   v \rightarrow 1, gdzie \displaystyle v,v' \in V_N , a \in A. Będziemy zamieniać produkcje występujące w gramatyce \displaystyle G na inne, o żądanej postaci, zgodnie z następująmi zasadami:

1. Produkcje typu \displaystyle  v \rightarrow v', gdzie \displaystyle v,v' \in V_N

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

\displaystyle V_N(v) = \{ v' \in V_N \; : \; v \rightarrow v_1 \rightarrow \ldots \rightarrow v_n \rightarrow v' \; w \; G \}

oraz zbiór produkcji

\displaystyle P(v) = \{ v \rightarrow xv" \; : \; x \neq 1 , \; \exists v' \in V_N(v) , v' \rightarrow xv" \in P \} \cup
\displaystyle \cup \{ v \rightarrow x \; : \; \exists v' \in V_N(v) , v' \rightarrow x \in P \}.

Dla każdego takiego symbolu \displaystyle v \in V_N usuwamy ze zbioru \displaystyle P wszystkie produkcje \displaystyle  v \rightarrow v' i wprowadzamy na to miejsce wszystkie produkcje ze zbioru \displaystyle P(v).

2. Produkcje typu \displaystyle  v \rightarrow x dla \displaystyle x \neq 1.

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

\displaystyle  v \rightarrow xv_x , \;\; v_x \rightarrow 1.

Zauważmy, że jeśli \displaystyle x\neq y, to \displaystyle v_x \neq v_y.

3. Produkcje typu \displaystyle  v \rightarrow x v' dla \displaystyle \mid x \mid > 1.

Jeśli \displaystyle  v \rightarrow a_1 \ldots a_n v' \in P, przy czym \displaystyle n \geq 2, to do alfabetu nieterminalnego \displaystyle V_N dodajemy nowe symbole \displaystyle  v_1 , \ldots v_n, produkcję \displaystyle  v \rightarrow a_1 \ldots a_n v' usuwamy ze zbioru \displaystyle P i

dodajemy produkcje:
\displaystyle  v \rightarrow a_1 v_1 , v_1 \rightarrow a_2 v_2 , \ldots ,v_{n-1} \rightarrow a_n v'.

Po opisanych powyżej trzech modyfikacjach gramatyki \displaystyle 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 \displaystyle \mathcal{A}  \displaystyle =(S,A,f,\{s_0\},T), przyjmując \displaystyle S= V_N, \displaystyle A= V_T oraz \displaystyle s_0 = v_0 i definiując następująco funkcję przejść: \displaystyle f(v,a) =  \{ v' \in V_N \; : \; v \rightarrow av' \in P \}. Przjmując \displaystyle T = \{ v \in V_N \; : \; v \rightarrow 1 \in P \} jako zbiór stanów końcowych, stwierdzamy, że automat \displaystyle \mathcal{A} rozpoznaje język

\displaystyle L(\mathcal{A})=\{w\in V_{T}^{*}\: :\: f(s_{0})\cap T\neq \emptyset \}=L.

Uzyskany rezultat, w świetle równości \displaystyle \mathcal{REG}(A^{*})=\mathcal{RE}C(A^{*}) , kończy dowód twierdzenia.

image:End_of_proof.gif

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 \displaystyle \mathcal{A}=(S,A,f,s_0,T) będzie automatem takim, że

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



Rysunek 7

Gramatyka \displaystyle G=(S,A,s_0,P), gdzie

\displaystyle P=\{s_0 \rightarrow as_1, s_0 \rightarrow bs_2, s_1 \rightarrow as_2, s_1 \rightarrow bs_0, s_1 \rightarrow 1, s_2 \rightarrow as_0, s_2 \rightarrow bs_1\}

akceptuje język \displaystyle L(\mathcal{A}).

Zauważmy, że język
\displaystyle L(\mathcal{A})=L(G)=\{ w \in A^* : \#_aw-\#_bw=1 mod 3\}.

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

\displaystyle P=\{v_0 \rightarrow av_0, v_0 \rightarrow ab, v_0 \rightarrow bv_1, v_1 \rightarrow 1 \}.

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

\displaystyle G'=(\{v_0,v_1,v_2,v_b\},\{a,b\},v_0,P'),

gdzie

\displaystyle P'=\{v_0 \rightarrow av_0, v_0 \rightarrow av_2, v_0 \rightarrow bv_1 , v_2 \rightarrow bv_b, v_1 \rightarrow 1 , v_b \rightarrow 1\}.

Niedeterministyczny automat \displaystyle \mathcal{A}_{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


\displaystyle L(G)=L(\mathcal{A}_{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ą \displaystyle \mathcal{REG}(A^{*}) .

Twierdzenie 2.3.

Dla dowolnego alfabetu \displaystyle A rodziny języków regularnych \displaystyle A^{*} oraz języków generowanych przez gramatyki regularne są równe, czyli \displaystyle \mathcal{REG}(A^{*})=\mathcal{L}_{3} .

Dowód

Odbicie zwierciadlane dowolnego języka \displaystyle L\in \mathcal{REG}(A^{*}) , czyli język \displaystyle \overleftarrow{L} należy również do rodziny \displaystyle \mathcal{REG}(A^{*}) , co oznacza, że \displaystyle \overleftarrow{L}\in \mathcal{RE}C(A^{*}) . Na podstawie twierdzenia 2.2. (patrz twierdzenie 2.2.) istnieje więc gramatyka prawoliniowa \displaystyle G taka, że \displaystyle \overleftarrow{L}=L(G) . A stąd wniosek, że \displaystyle L=\overleftarrow{\overleftarrow{L}}=L(\overline{G}) dla pewnej gramatyki \displaystyle \overline{G} typu (3). Zatem \displaystyle L\in \mathcal{L}_{3} .

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

image:End_of_proof.gif

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

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

\displaystyle \mathcal{REG}(A^{*})=\mathcal{REC}(A^{*})= \mathcal{L}_{3}

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