Informatyka MIMUW

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

---

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

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.

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.

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.

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.