Języki, automaty i obliczenia/Wykład 14: Języki maszyn Turinga i typu (0). Rozstrzygalność

From Studia Informatyczne

Spis treści

Języki maszyn Turinga i rodzina \displaystyle \mathcal{L}_{0}

Powstaje naturalne pytanie o związki pomiędzy klasą języków rozpoznawanych przez maszyny Turinga a klasami zadanymi poprzez gramatyki. Odpowiemy na to pytanie w tej części wykładu.

Twierdzenie 1.1

Każdy język akceptowany przez maszynę Turinga jest typu (0).

\displaystyle \mathcal{L}(MT)\subset \mathcal{L}_{0}.

Dowód

Niech \displaystyle L będzie językiem akceptowanym przez maszynę Turinga \displaystyle \mathbf{MT}=(\Sigma _{T},S,f,s_{0},S_{F}) , o której założymy, że \displaystyle f(s_{0},\#)=(s',\#,1) , jeśli para \displaystyle (s_{0},\#) należy do dziedziny funkcji przejść \displaystyle f maszyny Turinga. Założenie to nie ogranicza ogólności rozważań. Wyróżnimy pewien podzbiór \displaystyle \overline{S}_{F} zbioru stanów \displaystyle S , którego elementy, jak wskazuje oznaczenie, skojarzone są ze stanami końcowymi. Do zbioru \displaystyle \overline{S}_{F} należy każdy stan \displaystyle \overline{s}\in S , dla którego istnieje ciąg stanów \displaystyle s_{1}=\overline{s},...,s_{k} dla \displaystyle k\geqslant 1 taki, że \displaystyle (s_{i},\#)\rightarrow (s_{i+1},\#,0) dla \displaystyle k=1,...,k-1 oraz \displaystyle (s_{k},\#)\rightarrow (s,\#,1) , gdzie \displaystyle s\in S_{F} . Zauważmy, iż wraz ze stanem \displaystyle \overline{s} do zbioru \displaystyle \overline{S}_{F} należą wszystkie elementy ciągu \displaystyle s_{1}=\overline{s},...,s_{k} .

Określamy teraz gramatykę \displaystyle G=(V_{N},V_{T},v_{0},P) . Zbiór symboli nieterminalnych \displaystyle V_{N} zawiera wyłącznie następujące symbole:

  1. dla każdego stanu \displaystyle s\in S i \displaystyle a\in \Sigma _{T}\setminus \{\#\} symbole \displaystyle v_{sa},\: ^{\#}v_{sa},\: v_{sa}^{\#},\: ^{\#}v_{sa}^{\#},
  2. dla każdej litery \displaystyle a\in \Sigma _{T}\setminus \{\#\} symbole \displaystyle \, ^{\#}a i \displaystyle a^{\#},
  3. wszystkie elementy zbioru \displaystyle \Sigma _{T}\setminus (\Sigma _{I}\cup \{\#\}),
  4. symbole \displaystyle v_{0},\: v_{1} nie należące do \displaystyle \Sigma _{T}.

Zbiór praw \displaystyle P składa się z praw wymienionych poniżej:

  1. \displaystyle v_{0}\rightarrow \, ^{\#}v_{sa}^{\#} , \displaystyle v_{0}\rightarrow v_{1}v_{sa}^{\#}, jeśli \displaystyle f(s,a)=(\overline{s},b,1) dla pewnego \displaystyle b\in \Sigma _{T}\setminus \{\#\} , \displaystyle \overline{s}\in \overline{S}_{F} ,
  2. \displaystyle v_{1}\rightarrow \, ^{\#}a , \displaystyle v_{1}\rightarrow v_{1}a dla każdego \displaystyle a\in \Sigma _{T}\setminus \{\#\} ,
  3. \displaystyle v_{s_{1}c}b\rightarrow cv_{sa} , \displaystyle \, ^{\#}v_{s_{1}c}b\rightarrow \, ^{\#}cv_{sa} , \displaystyle v_{s_{1}c}b^{\#}\rightarrow cv^{\#}_{sa} , \displaystyle \, ^{\#}v_{s_{1}c}b^{\#}\rightarrow \, ^{\#}cv^{\#}_{sa}, jeśli \displaystyle f(s,a)=(s_{1},b,-1) i \displaystyle c\in \Sigma _{T}\setminus \{\#\} ,
  4. \displaystyle bv_{s_{1}c}\rightarrow v_{sa}c , \displaystyle \, ^{\#}bv_{s_{1}c}\rightarrow \, ^{\#}v_{sa}c , \displaystyle bv_{s_{1}c}^{\#}\rightarrow v_{sa}c^{\#} , \displaystyle \, ^{\#}bv_{s_{1}c}^{\#}\rightarrow \, ^{\#}v_{sa}c^{\#}, jeśli \displaystyle f(s,a)=(s_{1},b,1) i \displaystyle c\in \Sigma _{T}\setminus \{\#\} ,
  5. \displaystyle v_{s_{1}b}\rightarrow v_{sa} , \displaystyle \, ^{\#}v_{s_{1}b}\rightarrow \, ^{\#}v_{sa} , \displaystyle v_{s_{1}b}^{\#}\rightarrow v^{\#}_{sa} , \displaystyle \, ^{\#}v_{s_{1}b}^{\#}\rightarrow \, ^{\#}v^{\#}_{sa}, jeśli \displaystyle f(s,a)=(s_{1},b,0) ,
  6. \displaystyle v_{s_{1}b}^{\#}\rightarrow v^{\#}_{sa} , \displaystyle \, ^{\#}v_{s_{1}b}^{\#}\rightarrow \, ^{\#}v^{\#}_{sa} , jeśli istnieją \displaystyle s_{1}',...,s_{k}'\in S dla \displaystyle k\geqslant 1, takie że \displaystyle f(s,a)=(s_{1}',b,1) , \displaystyle f(s_{i}',\#)=(s_{i+1}',\#,0) dla \displaystyle i=1,...,k-1 oraz \displaystyle f(s_{k}',\#)=(s_{1},\#,-1) ,
  7. \displaystyle \, ^{\#}v_{s_{1}b}\rightarrow \, ^{\#}v_{sa} , \displaystyle \, ^{\#}v_{s_{1}b}^{\#}\rightarrow \, ^{\#}v^{\#}_{sa} , jeśli istnieją \displaystyle s_{1}',...,s_{k}'\in S dla \displaystyle k\geqslant 1 takie, że \displaystyle f(s,a)=(s_{1}',b,-1) , \displaystyle f(s_{i}',\#)=(s_{i+1}',\#,0) dla \displaystyle i=1,...,k-1 oraz \displaystyle f(s_{k}',\#)=(s_{1},\#,1) ,
  8. \displaystyle a^{\#}\rightarrow a dla wszystkich \displaystyle a\in \Sigma _{T}\setminus \{\#\} ,
  9. \displaystyle \, ^{\#}v_{sa}\rightarrow a , \displaystyle \, ^{\#}v_{sa}^{\#}\rightarrow a , jeśli \displaystyle f(s_{0},\#)=(s,\#,1) (porównaj założenie na początku dowodu),
  10. \displaystyle v_{0}\Rightarrow 1, jeśli \displaystyle 1\in L .

Określona powyżej gramatyka \displaystyle G jest gramatyką typu (0). Rozważmy teraz dowolne słowo \displaystyle w , dla którego istnieje wyprowadzenie w gramatyce \displaystyle G ze stanu początkowego \displaystyle v_{0} przy użyciu praw 1-7. Słowo \displaystyle w zawiera dokładnie jeden z następujących symboli \displaystyle v_{sa},\, ^{\#}v_{sa},v_{sa}^{\#} lub \displaystyle \, ^{\#}v_{sa}^{\#} . Pierwsza litera słowa \displaystyle w oznaczona jest markerem \displaystyle \# z lewej strony, a ostatnia litera słowa \displaystyle w oznaczona jest markerem \displaystyle \# ze strony prawej. Ponadto żadna z liter występujących pomiędzy pierwszą a ostatnią nie jest oznaczona markerem \displaystyle \# . Z każdym takim słowem kojarzymy konfigurację poprzez zastąpienie symbolu \displaystyle v_{sa} przez \displaystyle sa oraz przez dopisanie symbolu \displaystyle \# po lewej lub prawej stronie znaczonej przez ten marker litery, zgodnie z jego występowaniem. Jeśli np. \displaystyle w=\, ^{\#}v_{sa}^{\#} , to skojarzona konfiguracja jest postaci \displaystyle \#sa\# . Zauważmy, że jeśli słowa \displaystyle u i \displaystyle w są w powyższej formie, to fakt, iż \displaystyle u\mapsto^{*}w , jest równoważny stwierdzeniu, że z konfiguracji skojarzonej ze słowem \displaystyle w maszyna Turinga \displaystyle MT może przejść (bezpośrednie następstwo) do konfiguracji skojarzonej ze słowem \displaystyle u . Każdy krok obliczenia realizowanego przez \displaystyle MT ma swój odpowiednik - krok w wyprowadzeniu w gramatyce \displaystyle G . Z tym, że wobec praw 6 i 7 sekwencja obliczeń

\displaystyle vsa\#\rightarrow vbs_{1}'\#\rightarrow ...\rightarrow vbs_{k}'\#\rightarrow vs_{1}b\#

jest traktowana jako jeden krok w obliczeniu prowadzonym przez maszynę Turinga. Analogicznie traktujemy sekwencję z markerem \displaystyle \# występującym po lewej stronie. Ze stanu początkowego \displaystyle v_{0} gramatyki \displaystyle G można wyprowadzić wszystkie słowa \displaystyle w , dla których konfiguracja jest równa \displaystyle \#vsa\#, dla pewnego \displaystyle v\in (\Sigma _{I}\setminus \{\#\})^{*} oraz maszyna Turinga realizuje obliczenie:

\displaystyle sa\#\rightarrow bs_{1}'\#\rightarrow ...\rightarrow bs_{k}'\#\rightarrow b\#s_{1},\quad s_{1}\in S_{F}.

Wynika to z praw 1 i 2 skonstruowanej gramatyki \displaystyle G . Z kolei prawa typu 9 służą do zastąpienia symboli nieterminalnych typu \displaystyle \, ^{\#}v_{sa},\, ^{\#}v_{sa}^{\#} przez litery terminalne, a prawa typu 8 eliminują symbole nieterminalne typu \displaystyle a^{\#} . A zatem dla niepustego słowa \displaystyle w\in (\Sigma _{I}\setminus \{\#\})^{*} spełniona jest równoważność

\displaystyle v_{0}\mapsto_{G}^{*}w\: \Leftrightarrow \: s_{0}\#w\#\rightarrow _{TM}^{*}\#u\#s_{1},

gdzie \displaystyle u\in (\Sigma _{I}\setminus \{\#\})^{*} oraz \displaystyle s_{1}\in S_{F} . Prawo 10. zapewnia, że powyższa równoważność prawdziwa jest także dla słowa pustego \displaystyle 1 . A to kończy dowód tego twierdzenia.

image:End_of_proof.gif

Język \displaystyle L nazywamy rekurencyjnie przeliczalnym, jeśli istnieje efektywny algorytm wyliczający wyłącznie słowa z \displaystyle L . Przez efektywny algorytm rozumiemy skończony zbiór instrukcji, który w jednoznaczny sposób opisuje działanie tego algorytmu. Klasę języków rekurencyjnie przeliczalnych oznaczamy symbolem \displaystyle \mathcal{RP} .

Zauważmy, że każda gramatyka \displaystyle G typu (0) jest algorytmem wyliczającym wyłącznie słowa z \displaystyle L=L(G) . Dla każdej liczby naturalnej \displaystyle k można bowiem rozważyć skończony zbiór wyprowadzeń w \displaystyle G, rozpoczynających się od symbolu początkowego \displaystyle v_{0} i o długości równej \displaystyle k . Z tego zbioru można z kolei wybrać wyłącznie te wyprowadzenia, które kończą się słowem nad alfabetem terminalnym gramatyki \displaystyle G i tylko te słowa dodawać do listy składającej się na język \displaystyle L . Są to, jak łatwo zauważyć, wszystkie słowa języka \displaystyle L i nic ponadto. A zatem

Twierdzenie 1.2

Każdy język typu (0) jest językiem rekurencyjnie przeliczalnym, czyli \displaystyle \mathcal{L}_{0}\subset \mathcal{RP} .

Język \displaystyle L nazywamy rekurencyjnym, jeśli istnieje efektywny algorytm rozstrzygający dla każdego słowa \displaystyle w\in A^{*} jego przynależność do języka \displaystyle L . Klasę języków rekurencyjnych oznaczamy symbolem \displaystyle \mathcal{R} .

Klasa języków kontekstowych zawiera się istotnie w klasie języków rekurencyjnych, o czym przekonuje poniższe twierdzenie.

Twierdzenie 1.3

Każdy język kontekstowy jest językiem rekurencyjnym, czyli \displaystyle \mathcal{L}_{1}\subset \mathcal{R}.

Dowód

Niech \displaystyle L będzie dowolnym językiem kontekstowym. Istnieje więc gramatyka kontekstowa \displaystyle G=(V_{N},V_{T},v_{0},P) taka, że \displaystyle L=L(G) . Bezpośrednio z definicji gramatyki kontekstowej wynika, iż słowo puste \displaystyle 1\in L wtedy i tylko wtedy, gdy \displaystyle v_{0}\rightarrow 1\in P . Załóżmy teraz, że dane jest słowo \displaystyle w\in V^{*}_{T} , o którym mamy zadecydować, czy należy do języka \displaystyle L . W tym celu rozważmy wszystkie ciągi słów

\displaystyle y_{0}=v_{0},\: y_{1},...,y_{n-1},\: y_{n}=w

o tej własności, że \displaystyle y_{i}\in (V_{N}\cup V_{T})^{*} są parami różne, dla \displaystyle i=0,...,n , \displaystyle n\geqslant 1 oraz \displaystyle \mid y_{i}\mid \leqslant \mid y_{i+1}\mid . Ilość takich ciągów jest skończona i słowo \displaystyle w\in L wtedy i tylko wtedy, gdy wśród powyższych ciągów znajdziemy choć jeden taki, że tworzy wyprowadzenie w gramatyce \displaystyle G . Czyli

\displaystyle y_{0}=v_{0}\rightarrow y_{1}\rightarrow ...\rightarrow y_{n-1}\rightarrow y_{n}=w.

Ponieważ ilość ciągów podlegających rozważaniom jest skończona oraz ponieważ stwierdzenie, czy pomiędzy dowolnymi słowami zachodzi relacja \displaystyle \rightarrow , sprowadza się do przeszukania skończonego zbioru praw \displaystyle P , efektywnie rozstrzygniemy, czy \displaystyle w należy do języka \displaystyle L, czy też nie.

image:End_of_proof.gif

Uzyskane dotąd rezultaty możemy podsumować następująco:

\displaystyle \mathcal{L}(MT)\subset \mathcal{L}_{0}\subset \mathcal{RP}.

W określeniu języka rekurencyjnie przeliczalnego oraz języka rekurencyjnego wystąpiło pojęcie efektywnego algorytmu, efektywnej procedury. Pojęcie to, intuicyjnie dość jasne, nie zostało precyzyjnie określone. Co za tym idzie, dla matematycznie poprawnych definicji języka rekurencyjnie przeliczalnego i języka rekurencyjnego należałoby sformalizować pojęcie algorytmu. W dotychczasowych rozważaniach intuicja efektywnej procedury była o tyle wystarczająca, że naszym celem było wskazanie istnienia takiej procedury. W sytuacji, gdyby naszym celem było wykazanie, że taka procedura nie istnieje, formalizacja tego pojęcia byłaby wręcz konieczna. We wszystkich takich przypadkach powszechnie przyjmuje się, że maszyna Turinga jest właśnie taką formalizacją. Na zdefiniowaną w poprzednim wykładzie maszynę Turinga można spojrzeć jako na algorytm, efektywną procedurę dającą odpowiedź pozytywną lub negatywną w zależności od akceptacji lub nieakceptowania słowa wejściowego. Proces obliczenia prowadzony przez maszynę Turinga zgadza się z intuicyjnym rozumieniem algorytmu. O tym, że każda efektywna procedura jest reprezentowana przez pewną maszynę Turinga, mówi, powszechnie przyjęta jako prawdziwa, teza Churcha.

Teza Churcha

Każda efektywna procedura (algorytm) da się opisać przez maszynę Turinga.

Konsekwencją przyjęcia tezy Churcha jest inkluzja \displaystyle \mathcal{RP}\subset \mathcal{L}(MT) . Biorąc pod uwagę udowodnione powyżej twierdzenia, mamy:

\displaystyle \mathcal{L}(MT)\subset \mathcal{L}_{0}\subset \mathcal{RP},

co ostatecznie prowadzi do równości \displaystyle \mathcal{L}_{0}=\mathcal{L}(MT) .

Rodziny \displaystyle \mathcal{L}_{1} i \displaystyle \mathcal{L}_{0} - zamkniętość na działania

Dla kompletności tej części wykładu przedstawimy własności zamkniętości rodziny języków kontekstowych \displaystyle \mathcal{L}_{1} i języków typu (0) \displaystyle \mathcal{L}_{0} ze względu na najczęściej używane operacje. W niektórych przypadkach dowody dotyczące obu klas są takie same. W dowodach posłużymy się specjalną postacią gramatyk, a mianowicie taką, w której symbole terminalne występują tylko po prawej stronie. Prawdziwe bowiem jest twierdzenie

Twierdzenie 2.1

Dla każdej gramatyki istnieje równoważna gramatyka tego samego typu taka, że każda produkcja, w której występuje symbol terminalny \displaystyle a , jest postaci \displaystyle v\longrightarrow a .

Elementarny dowód tej własności pozostawiamy jako zadanie domowe.

Twierdzenie 2.2

Rodziny \displaystyle \mathcal{L}_{0} i \displaystyle \mathcal{L}_{1} są zamknięte ze względu na:

  1. sumę mnogościową,
  2. iloczyn mnogościowy,
  3. katenację,
  4. iterację \displaystyle *,
  5. odbicie zwierciadlane.

Dowód

1. Niech dla \displaystyle i=1,2  \displaystyle G_{i}=(V_{N}^{i},V_{T},v_{0}^{i},P_{i}) będą gramatykami typu \displaystyle (1) (odpowiednio typu \displaystyle (0) ) takimi, że \displaystyle V_{N}^{1}\cap V_{N}^{2}=\emptyset . I niech \displaystyle L_{i}=L(G_{i}) . Określamy gramatykę \displaystyle G typu \displaystyle (1) (typu \displaystyle (0) ) generującą język \displaystyle L_{1}\cup L_{2} .

Jeśli \displaystyle 1\notin L_{1}\cup L_{2} , to przyjmujemy:

\displaystyle G=(V_{N}^{1}\cup V_{N}^{2}\cup \left\{ v_{0}\right\} ,V_{T},v_{0},P_{1}\cup P_{2}\cup \left\{ v_{0}\rightarrow v_{0}^{1},\, v_{0}\rightarrow v_{0}^{2}\right\} ).

Zauważmy, że wówczas w żadnej z gramatyk nie ma prawa wymazującego. Jeśli natomiast \displaystyle 1\in L_{1}\cup L_{2} , to konstruujemy gramatykę \displaystyle G dla języków \displaystyle L_{1}\setminus \left\{ 1\right\} i \displaystyle L_{2}\setminus \left\{ 1\right\} , jak powyżej, a następnie dodajemy nowy symbol początkowy \displaystyle \overline{v}_{0} i prawa \displaystyle \overline{v}_{0}\rightarrow v_{0},\, \overline{v}_{0}\rightarrow 1 .

2. Przecięcie udowodnimy tylko dla języków typu \displaystyle (0) . Dowód dla języków kontekstowych został przeprowadzony wcześniej.

Niech dla \displaystyle i=1,2  \displaystyle G_{i}=(V_{N}^{i},V_{T},v_{0}^{i},P_{i}) będą gramatykami typu \displaystyle (0) takimi, że \displaystyle V_{N}^{1}\cap V_{N}^{2}=\emptyset . Niech \displaystyle L_{i}=L(G_{i}) . Określamy gramatykę \displaystyle G typu \displaystyle (0) generującą język \displaystyle L_{1}\cap L_{2}, przyjmując:

\displaystyle G=(V_{N}^{1}\cup V_{N}^{2}\cup V_{N},V_{T},v_{0},P_{1}\cup P_{2}\cup P),

gdzie: \displaystyle V_{N}=\left\{ v_{a}\, :\, a\in V_{T}\right\} \cup \left\{ v_{0},\overline{v}_{1},\overline{v}_{2}\right\} , a do zbioru \displaystyle P należą prawa:
(1) \displaystyle v_{0}\rightarrow \overline{v}_{1}v_{0}^{1}\overline{v}_{2}v_{0}^{2}\overline{v}_{1},
(2) \displaystyle \overline{v}_{2}a\rightarrow v_{a}\overline{v}_{2} dla \displaystyle \forall a\in V_{T},
(3) \displaystyle bv_{a}\rightarrow v_{a}b dla \displaystyle \forall a,b\in V_{T},
(4) \displaystyle \overline{v}_{1}v_{a}a\rightarrow a\overline{v}_{1} dla \displaystyle \forall a\in V_{T},
(5) \displaystyle \overline{v}_{1}\overline{v}_{2}\overline{v}_{1}\rightarrow 1.
Przy pomocy prawa (1) i wszystkich praw ze zbioru \displaystyle P_{1}\cup P_{2} można wygenerować zbiór słów:

\displaystyle \left\{ \overline{v}_{1}w_{1}\overline{v}_{2}w_{2}\overline{v}_{1}\, :\, w_{1}\in L_{1},\, w_{2}\in L_{2}\right\} .

Z dowolnego słowa należącego do tego zbioru, korzystając z praw (2)-(4), można wyprowadzić słowo \displaystyle w_{1}\overline{v}_{1}\overline{v}_{2}\overline{v}_{1} wtedy i tylko wtedy, gdy \displaystyle w_{1}=w_{2} . Korzystając z prawa (5), dostajemy słowo \displaystyle w_{1} . A więc \displaystyle L(\overline{G})=L_{1}\cap L_{2} .

3. Niech dla \displaystyle i=1,2  \displaystyle G_{i}=(V_{N}^{i},V_{T},v_{0}^{i},P_{i}) będą tak jak poprzednio gramatykami typu \displaystyle (1) ( \displaystyle (0) ) takimi, że \displaystyle V_{N}^{1}\cap V_{N}^{2}=\emptyset oraz spełniającymi warunki powyższego twierdzenia. Niech \displaystyle L_{i}=L(G_{i}) . Określamy gramatykę \displaystyle G odpowiednio typu \displaystyle (1) ( \displaystyle (0) ) generującą język \displaystyle L_{1}L_{2} .

Jeśli \displaystyle 1\notin L_{1}\cup L_{2} , to przyjmujemy:

\displaystyle G=(V_{N}^{1}\cup V_{N}^{2}\cup \left\{ v_{0}\right\} ,V_{T},v_{0},P_{1}\cup P_{2}\cup \left\{ v_{0}\rightarrow v_{0}^{1}v_{0}^{2}\right\} ).

Jeśli \displaystyle 1\in L_{1}\cup L_{2} , to oznaczamy \displaystyle L_{1}'=L_{1}\setminus \left\{ 1\right\} ,\; \; L_{2}'=L_{2}\setminus \left\{ 1\right\} . Wówczas:

\displaystyle L_{1}L_{2}=\left\{ \begin{array} {lll} L_{1}'L_{2}'\cup L_{1}', & gdy & 1\in L_{2},\: 1\notin L_{1},\\ L_{1}'L_{2}'\cup L_{2}', & gdy & 1\in L_{1},\: 1\notin L_{2},\\ L_{1}'L_{2}'\cup L_{1}'\cup L_{2}'\cup \left\{ 1\right\},  & gdy & 1\in L_{1},\: 1\in L_{2}. \end{array} \right.

Wykorzystując poprzednią konstrukcję i zamkniętość ze względu na sumę w każdym z tych przypadków, otrzymujemy gramatykę generującą katenację języków \displaystyle L_{1} i \displaystyle L_{2} .

4. Niech \displaystyle G=(V_{N},V_{T},v_{0},P) będzie gramatyką typu \displaystyle (1) (typu \displaystyle (0) ) taką, że symbole terminalne nie występują po lewej stronie żadnej produkcji z \displaystyle P . Załóżmy też, że \displaystyle 1\notin L=L(G) . Gramatyka

\displaystyle \overline{G}=(V_{N}\cup \left\{ \overline{v}_{0},\overline{v}_{1}\right\} ,V_{T},\overline{v}_{0},\overline{P}),

gdzie

\displaystyle \overline{P}=P\cup \begin{array} [t]{l} \left\{ \overline{v}_{0}\rightarrow 1,\: \overline{v}_{0}\rightarrow v_{0},\: \overline{v}_{0}\rightarrow \overline{v}_{1}v_{0}\right\} \cup \\ \left\{ \overline{v}_{1}a\rightarrow \overline{v}_{1}v_{0}a\, :\, a\in V_{T}\right\} \cup \\ \left\{ \overline{v}_{1}a\rightarrow v_{0}a\, :\, a\in V_{T}\right\} \end{array}

generuje język \displaystyle L^{*} . Jeśli \displaystyle 1\in L , to usuwamy prawo wymazujące \displaystyle v_{0}\rightarrow 1 i dla języka \displaystyle L\setminus \left\{ 1\right\} konstruujemy gramatykę \displaystyle \overline{G} . Z faktu, że \displaystyle (L\cup \left\{ 1\right\} )^{*}=L^{*} , wynika, że również \displaystyle L(\overline{G})=L^{*} .

5. Jeśli \displaystyle G=(V_{N},V_{T},v_{0},P) jest gramatyką typu \displaystyle (1) (typu \displaystyle (0) ) taką, że \displaystyle L(G)=L , to gramatyka \displaystyle \overleftarrow{G}=(V_{N},V_{T},v_{0},\overleftarrow{P}) , gdzie \displaystyle \overleftarrow{P}=\left\{ \overleftarrow{x}\rightarrow \overleftarrow{y}\, :\, x\rightarrow y\in P\right\} generuje język \displaystyle \overleftarrow{L} .

image:End_of_proof.gif

Zauważmy na koniec, że rodzina \displaystyle \mathcal{L}_{0} nie jest zamknięta ze względu na uzupełnienie. Stwierdzenie to wynika z przyjęcia jako obowiązujacej tezy Churcha, która w tym wypadku implikuje równość rodziny języków \displaystyle \mathcal{L}_{0} i rodziny języków rekurencyjnie przeliczalnych oraz z faktu, iż istnieje język rekurencyjnie przeliczalny, którego uzupełnienie nie jest rekurencyjnie przeliczalne. Ten ostatni fakt podajemy bez dowodu. Dodajmy, że własność zamkniętości ze względu na uzupełnienie dla rodziny \displaystyle \mathcal{L}_{1} przez długi czas pozostawała problemem otwartym. Dopiero w roku 1987 udowodniono, iż własność ta jest spełniona dla języków kontekstowych. Podsumowanie własności zamkniętości ze względu na działania dla różnych klas języków hierarchii Chomsky'ego zawarte jest w poniższej tabeli:

         3      2      1      0   
   \displaystyle\cup      T      T      T      T   
   \displaystyle\cdot      T      T      T      T   
   \displaystyle\star      T      T      T      T   
   \displaystyle\setminus      T      N      T      N   
   \displaystyle\cap      T      N      T      T   

Na koniec podamy twierdzenie o wzajemnych relacjach pomiędzy rodzinami języków z hierarchii Chomsky'ego. Dowód tego twierdzenia wynika w części z definicji typów gramatyk wprowadzonych na wykładzie 2, a w części z udowodnionych własności poszczególnych rodzin języków z hierarchii Chomsky'ego (zakładając obowiązywanie tezy Churcha).

Twierdzenie 2.3

Rodziny języków hierarchii Chomsky'ego spełniają następujące relacje:

\displaystyle \mathcal{L}_{0}\subseteq \! \! \! \! \! \! _{/}\, \mathcal{L}_{1} \subseteq \! \! \! \! \! \! _{/}\, \mathcal{L}_{2} \subseteq \! \! \! \! \! \! _{/}\, \mathcal{L}_{3}.

Problemy rozstrzygalne

W poprzednim wykładzie uzasadniliśmy, że dla każdej deterministycznej maszyny Turinga jesteśmy w stanie wskazać taką, która akceptuje dany język i jednocześnie zatrzymuje się tylko na słowach akceptowanych. Wymagało to przejścia przez maszynę niedeterministyczną, a następnie jej symulację na maszynie deterministycznej. Z tego powodu ograniczamy się w dalszej części wykładu tylko do tego typu maszyn Turinga (akceptacja=stop). Jak to uzasadniono wcześniej, przy założeniu tezy Churcha, maszyna Turinga może być rozpatrywana jako matematycznie ścisła definicja algorytmu.

Pojęcie rozstrzygalnego problemu zostało wprowadzone wcześniej, na innym wykładzie, i jest ono znane. Przypomnijmy więc tylko, że rozstrzygalność, czy też nierozstrzygalność, odnosi się do pewnej klasy, którą tworzą określone przypadki ustalonego problemu. Jeśli istnieje algorytm, który rozwiązuje taki problem dla wszystkich przypadków w tej klasy, to mówimy, że problem jest rozstrzygalny (w tej klasie). Zatem taki algorytm jest uniwersalnym sposobem rozwiązywania problemu dla wszystkich danych wejściowych określających poszczególne przypadki w tej klasie. Jak łatwo zauważyć dla ustalenia rozstrzygalności problemu wystarczy się opierać na intuicyjnym pojęciu algorytmu. Są jednak takie problemy, dla których nie istnieje, w rozważanej klasie przypadków, uniwersalny sposób ich rozwiazywania. Takie problemy nazywamy nierozstrzygalnymi w danej klasie. Aby wykazać nierozstrzygalność jakiegoś problemu, nieodzownym jest sformalizowanie pojęcia algorytmu. Standardowo taką formalizacją jest, o czym wspomniano już wcześniej, maszyna Turinga.

Zwróćmy uwagę, że maszyna Turinga akceptuje języki, gdy tymczasem przyzwyczajeni jesteśmy, że algorytmy (programy) rozwiązują pewne, niekiedy bardzo skomplikowane, problemy (określone przy pomocy list, kolejek, grafów itp.). Zwracamy zatem uwagę na fakt, że w przypadku maszyny Turinga musimy wykonać wstępne umowne kodowanie naszego problemu. W tym przypadku rozważany język określa te spośród "sensownych" kodowań, które stanowią rozwiązanie postawionego problemu. Z drugiej strony maszyna, akceptując słowo \displaystyle \sharp w_1 \$ w_2 \sharp, może informować nas o tym, że wynikiem obliczeń numerycznych na danych zakodowanych w \displaystyle w_1 rzeczywiście jest liczba zakodowana w \displaystyle w_2 itp.

Dla ilustracji powyższych dywagacji rozważmy problem skończoności w klasie jezyków regularnych. Problem ten jest rozstrzygalny, bo w oparciu o lemat o pompowaniu można skonstruować algorytm, który dla dowolnego języka regularnego rozstrzygnie, czyli odpowie twierdząco lub przecząco na pytanie o jego skończoność. W tym przypadku można np. przyjąć, że jako słowo wejściowe podajemy zakodowany opis gramatyki generującej język.

Nierozstrzygalność algorytmiczna problemu w ustalonej klasie nie oznacza, podkreślmy, niemożliwości rozwiązania konkretnego zadania z tej klasy. Nierostrzygalność oznacza niemożliwość rozwiązania za pomocą tego samego algorytmu, tej samej metody, wszystkich przypadków tego problemu należących do danej klasy.

W zamieszczonej poniżej tabeli przedstawiamy najczęściej rozważane pod kątem rozstrzygalności problemy z dziedziny języków formalnych w ramach hierarchii Chomsky'ego. Litera R oznacza rozstrzygalność problemu, N nierostrzygalność, a znak - pojawiający się przy problemie jednoznaczności oznacza, że problemu tego nie formułuje się dla gramatyk kontekstowych i typu (0):

własność (3) (2) (1) (0)
należenie \displaystyle w\in L R R R N
inkluzja \displaystyle L_{1}\subset L_{2} R N N N
równoważność R N N N
pustość \displaystyle L=\emptyset R R N N
nieskończoność \displaystyle card\, L=\aleph _{0} R R N N
jednoznaczność gramatyki R N - -

Najczęściej używaną metodą dowodzenia nierozstrzygalności problemu \displaystyle P jest redukcja tego problemu do innego, powiedzmy \displaystyle P' , dla którego nierozstrzygalność została ustalona wcześniej. Redukcja taka prowadzi do sformułowania implikacji:

jeśli \displaystyle P byłby rozstrzygalny, to i \displaystyle P' byłby rozstrzygalny.

A ponieważ to ostatnie (następnik implikacji) nie jest prawdą, więc problem \displaystyle P nie jest rozstrzygalny.

Należy w tym miejscu podkreślić fakt, że dowody nierozstrzygalności problemów uniwersalnych (takich jak problem Posta rozważany dalej) wiążą się z konstrukcją odpowiednich maszyn Turinga, kodowaniem problemu, a następnie dowodem uzasadniającym, że problem jest rzeczywiście nierozstrzygalny. Tematyka ta wykracza poza ramy wykładu. Z tego też powodu ograniczymy się tutaj do zaprezentowania jednego ze znanych problemów nierozstrzygalnych bez dowodu nierozstrzygalności.

Najczęściej występującym w literaturze problemem nierozstrzygalnym jest, bez wątpienia, problem Posta przedstawiony poniżej.

 

Problem Posta

Dla dowolnego alfabetu \displaystyle A , o co najmniej dwóch elementach ( \displaystyle \sharp A\geqslant 2 ), załóżmy, iż dana jest, tak zwana, lista słów, a dokładniej: par słów \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right), gdzie \displaystyle u_{i},w_{i}\in A^{+} , \displaystyle n\in \Bbb N . Mówimy, że taka lista ma własność Posta (problem Posta ma rozwiązanie), jeśli istnieje ciąg indeksów \displaystyle i_{1},\ldots ,i_{k}\in \{1,...,n\} taki, że

\displaystyle u_{i_{1}}\ldots u_{i_{k}}=w_{i_{1}}\ldots w_{i_{k}}.

Jest to w ogólnym przypadku problem nierozstrzygalny.

Problem ten można sformułować równoważnie następująco. Niech \displaystyle A będzie alfabetem interpretowanym jako zbiór indeksów, a \displaystyle B dowolnym alfabetem. Niech \displaystyle h:A^{*}\longrightarrow B^{*},\: g:A^{*}\longrightarrow B^{*} będą dowolnymi homomorfizmami. Problem Posta, inaczej sformułowany, polega na odpowiedzi na pytanie, czy istnieje słowo \displaystyle x\in A^{+} takie, że \displaystyle h(x)=g(x) .

Dwa kolejne przykłady ilustrują technikę redukcji pewnych problemów do problemu Posta. W efekcie uzyskujemy nierozstrzygalność w sposób opisany powyżej.

Twierdzenie 3.1

W klasie gramatyk bezkontekstowych problem niejednoznaczności jest nierozstrzygalny.

Dowód

Udowodnimy, że problem jest nierozstrzygalny dla gramatyk bezkontekstowych generujących języki nad alfabetem dwuelementowym \displaystyle A=\{a,b\} . Oznaczmy \displaystyle B=\{d,e\} i określmy homomorfizm \displaystyle h:B^{*}\longrightarrow A^{*} , przyjmując \displaystyle h(d)=ba^{2} oraz \displaystyle h(e)=ba^{3} . Niech \displaystyle u będzie ciągiem \displaystyle u_{1},...,u_{n}\in B^{+} dowolnie wybranych i ustalonych słów. Dla dowolnej liczby naturalnej \displaystyle i>0 niech \displaystyle \overline{i}=de^{i} . Określony poniżej język

\displaystyle L_{u}=\{h(\overline{i_{1}}).....h(\overline{i_{k}})bah(u_{i_{k}}),...,h(u_{i_{1}})\in A^{*}\: :\: k\geqslant 1,\: 1\leqslant i_{j}\leqslant n\}

jest językiem bezkontekstowym, jako generowany przez gramatykę \displaystyle G_{u}=(V_{N},V_{T},v_{0},P_{u}) , dla której

\displaystyle V_{N}=\{v_{u}\},\: V_{T}=\{a,b\},\: v_{0}=v_{u} oraz \displaystyle P_{x}=\{v_{u}\rightarrow h(\overline{i})v_{u}h(u_{i}),\: v_{u}\rightarrow h(\overline{i})bah(u_{i})\} .

Niech teraz \displaystyle u i \displaystyle w oznaczają ciągi dowolnie wybranych i ustalonych słów \displaystyle u_{1},...,u_{n}\in B^{+} i \displaystyle w_{1},...,w_{n}\in B^{+} . Tworzą one listę słów \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right), . Zatem zasadne jest postawienie pytania, czy lista ta ma własność Posta. Niech \displaystyle G_{u} oraz \displaystyle G_{w} będą gramatykami bezkontekstowymi określonymi tak jak powyżej. Gramatyka \displaystyle G=(\{v_{0},v_{u},v_{w}\},\{a,b\},v_{0},P) , gdzie \displaystyle P=\{v_{0}\rightarrow v_{u},\: v_{0}\rightarrow v_{w}\}\cup P_{u}\cup P_{w} jest bezkontekstowa. Gramatyka ta jest niejednoznaczna wtedy i tylko wtedy, gdy \displaystyle L_{u}\cap L_{y}\neq \emptyset . Ten ostatni warunek równoważny jest istnieniu liczb \displaystyle i_{1},...,i_{k}\in \Bbb N takich, że \displaystyle u_{i_{1}}.....u_{i_{k}}=w_{i_{1}}.....w_{i_{k}}, czyli własności Posta listy \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right) .Ostatecznie więc rozstrzygalność problemu niejednoznaczności w klasie gramatyk bezkontekstowych prowadziłaby do rozstrzygalności własności Posta.

image:End_of_proof.gif

Dla drugiego przykładu przyjmijmy jako alfabety \displaystyle A_{2}=\left\{ a,b\right\} ,\: A_{3}=\left\{ a,b,c\right\} oraz określmy język

\displaystyle L=\left\{ v_{1}cv_{2}c\overleftarrow{v}_{2}c\overleftarrow{v}_{1}\, :\, v_{1},v_{2}\in A_{2}^{*}\right\}.

Ustalmy listę Posta \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right) nad alfabetem \displaystyle A_{2} , gdzie \displaystyle u_{i},w_{i}\in A_{2}^{+} . Wprowadzamy teraz języki \displaystyle L_{u},\: L_{w}\: L_{PP} nad alfabetem \displaystyle A_{3}, przyjmując:

\displaystyle \aligned L_{u} &= \left\{ ba^{i_{k}}b\ldots ba^{i_{1}}cu_{i_{1}}\ldots u_{i_{k}}\, :\, k\geqslant 1,1\leqslant i_{j}\leqslant n\right\} \\ L_{w} &= \left\{ ba^{i_{k}}b\ldots ba^{i_{1}}cw_{i_{1}}\ldots w_{i_{k}}\, :\, k\geqslant 1,1\leqslant i_{j}\leqslant n\right\} \endaligned

oraz definiujemy język

\displaystyle L_{PP}=L_{u}c\overleftarrow{L}_{w}.

Określone powyżej języki nad alfabetem \displaystyle A_{3} mają własności konieczne do zastosowania lematu, który przytoczymy bez dowodu.

Lemat 3.1

Języki \displaystyle L,\: L_{PP},\: A_{3}^{*}\setminus L,\: A_{3}^{*}\setminus L_{PP} są bezkontekstowe.

Dla języków \displaystyle L i \displaystyle L_{PP} uzasadnienie ich bezkontekstowości jest proste poprzez konstrukcję odpowiednich gramatyk. Aby uzyskać bezkontekstowość ich uzupełnień, należy podzielić rozważane języki na rozłączne podzbiory i konstruować gramatyki bezkontekstowe dla tych wyróżnionych podzbiorów, a w końcu wykorzystać fakt, że suma języków bezkontekstowych jest językiem bezkontekstowym.

Zauważmy teraz, że istnienie rozwiązania problemu Posta nad alfabetem \displaystyle A_{3} jest równoważne temu, że \displaystyle L_{PP}\cap L\neq \emptyset .

Jeśli bowiem \displaystyle L_{PP}\cap L\ni ba^{i_{k}}\ldots ba^{i_{1}}cu_{i_{1}}\ldots u_{i_{k}}c\overleftarrow{w_{i_{1}}\ldots w_{i_{k}}}ca^{i_{1}}b\ldots a^{i_{k}}b , gdzie \displaystyle k\geqslant 1,1\leqslant i_{j}\leqslant n , to oczywiście \displaystyle u_{i_{1}}\ldots u_{i_{k}}=w_{i_{1}}\ldots w_{i_{k}} . Jeśli ciąg \displaystyle i_{1},\ldots ,i_{k} jest rozwiązaniem problemu Posta, to \displaystyle (i_{1},\ldots ,i_{k})(i_{1},\ldots ,i_{k}) też. Zatem jeśli \displaystyle L_{PP}\cap L\neq \emptyset , to język \displaystyle L_{PP}\cap L jest nieskończony.

Wobec nierozstrzygalności problemu Posta wnioskujemy, że nierozstrzygalny jest problem pustości i problem nieskończoności przecięcia \displaystyle L_{1}\cap L_{2} w klasie języków bezkontekstowych.