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).
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:
Zbiór praw \(\displaystyle P\) składa się z praw wymienionych poniżej:
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ń
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:
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ść
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.
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
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
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.
Uzyskane dotąd rezultaty możemy podsumować następująco:
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:
co ostatecznie prowadzi do równości \(\displaystyle \mathcal{L}_{0}=\mathcal{L}(MT)\) .
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:
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:
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:
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:
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:
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:
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
gdzie
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}\) .
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:
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
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
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.
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
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:
oraz definiujemy język
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.