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

Ćwiczenia 13

Ćwiczenie 1

W trakcie wykładu rozważaliśmy język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{3^k\: : \: k=i\cdot j } dla pewnych $\displaystyle i,j>1\rbrace ,$

wykazując, że $\displaystyle L\in$ NP .

Uzasadnij, że także $\displaystyle L\in$ P $\displaystyle .$

Wskazówka

Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie $\displaystyle i,j>1$, dla których $\displaystyle k=i\cdot j$

Rozwiązanie

Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie $\displaystyle k^{2}$ (wielomianową ilość) mnożeń. Sama weryfikacja zależności $\displaystyle k=i\cdot j$ (według uzasadnienia z wykładu) jest wykonywana w czasie wielomianowym.

Pozostaje zaprojektować deterministyczną maszynę generującą ciągi. Można to zrobić według schematu (maszyna czterotaśmowa):

1. Taśma nr $\displaystyle 1$ jest tylko do odczytu. Mamy na niej słowo $\displaystyle 3^{k}$.
2. Rozpocznij od zapisania słowa $\displaystyle 11$ na taśmie nr $\displaystyle 2$ i słowa $\displaystyle 22$ na taśmie nr $\displaystyle 3$.
3. Przepisz słowa na taśmę nr $\displaystyle 4$ według kolejności taśm $\displaystyle 2,3,1$.
4. Sprawdź na taśmie nr $\displaystyle 4$, czy $\displaystyle k=i\cdot j$. Jeśli tak, to akceptuj. Inaczej krok następny.
5. Dopisz symbol $\displaystyle 1$ na taśmie nr $\displaystyle 2$. Gdy powstało słowo dłuższe niż $\displaystyle k$, dopisz symbol $\displaystyle 2$ na taśmie nr $\displaystyle 3$, a słowo na taśmie nr $\displaystyle 2$ usuń i zapisz na niej słowo $\displaystyle 11$.
6. Jeśli słowo na taśmie nr $\displaystyle 3$ jest dłuższe niż $\displaystyle k$, to odrzuć. W przeciwnym przypadku przejdź do kroku 3.

Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr $\displaystyle 2$ (licznik 1) i $\displaystyle 3$ (licznik 2) jako liczniki, a na taśmie $\displaystyle 4$ wykonuj symulacje. Zacznij od stanu liczników na $\displaystyle 2$ i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej $\displaystyle 2$) i zwiększ licznik $\displaystyle 2$. Gdy on także się przepełni, to iloczyn stanów liczników przekracza $\displaystyle k$, zatem można zakończyć generowanie ciągów.

W oczywisty sposób otrzymujemy, że ilość wymaganych kroków czasowych maszyny jest ograniczona przez wielomian (dla dużych $\displaystyle n$). Dla małych $\displaystyle n$ możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. Zatem $\displaystyle L\in$ P .

Ćwiczenie 2

Uzasadnij, że funkcja $\displaystyle s(n)=3n$ jest konstruowalna pamięciowo.

Wskazówka

Przypomnij sobie uzasadnienie dla funkcji $\displaystyle 2n$ z wykładu.

Rozwiązanie

Bierzemy maszynę $\displaystyle MT_{4}$ z wykładu konstruującą funkcję $\displaystyle 2n$. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez $\displaystyle I$ oraz $\displaystyle S$). Drugą taśmę realizujemy poprzez rozszerzenie alfabetu. Jest to spowodowane faktem, że w definicji konstruowalności pamięciowej wymagane jest istnienie jednotaśmowej deterministycznej maszyny Turinga. Konstruujemy maszynę $\displaystyle {\mathcal {M}}$ według schematu:

1. Jeśli słowo wejściowe jest puste, to stop.
2. Jeśli słowo wejściowe jest inne niż $\displaystyle 1^{n}$, to odrzuć.
3. Przepisz słowo wejściowe tak aby znajdowało się na taśmie $\displaystyle I$, a taśma $\displaystyle S$ była pusta (gdy zaczynamy symulować dwie taśmy, musimy przejść do innego zestawu symboli, w którym rozróżniamy taśmy).
4. Kopiujemy słowo wejściowe na taśmę $\displaystyle S$.
5. Symulujemy maszynę $\displaystyle MT_{4}$ na taśmie $\displaystyle S$.
6. Dopisujemy do taśmy $\displaystyle S$ słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie $\displaystyle 3n$ komórek taśmy.
7. Zamieniamy symbole na $\displaystyle 1$ (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy

do konfiguracji końcowej $\displaystyle s_{1}\in S_{F}$.

Po zakończeniu cyklu doszliśmy do konfiguracji $\displaystyle \sharp s_{1}1^{3n}\sharp$, co było wymagane w definicji.

Ćwiczenie 3

Uzasadnij, że funkcja $\displaystyle s(n)=3^{n}$ jest konstruowalna pamięciowo.

Wskazówka

Wykorzystaj konstruowalność pamięciową funkcji $\displaystyle g(n)=3n$.

Rozwiązanie

Wykorzystujemy trzy taśmy ($\displaystyle I$, $\displaystyle C$, $\displaystyle S$) oraz maszynę $\displaystyle {\mathcal {M}}$ konstruującą pamięciowo funkcję $\displaystyle g(n)=3n$. Docelowa maszyna $\displaystyle {\mathcal {N}}$ działa według schematu:

1. Jeśli słowo początkowe jest puste, wypisz $\displaystyle 1$ i zatrzymaj się. Inaczej wykonaj następny krok.
2. Jeśli słowo wejściowe jest inne niż $\displaystyle 1^{n}$, to odrzuć.
3. Na taśmie $\displaystyle I$ wypisz słowo wejściowe, na taśmach $\displaystyle C$ i $\displaystyle S$ wypisz słowo $\displaystyle 1$.
4. Wykonaj symulację maszyny $\displaystyle {\mathcal {M}}$ na taśmie $\displaystyle S$ oraz dopisz symbol $\displaystyle 1$ do taśmy $\displaystyle C$ (po jednym przebiegu ilość symboli na taśmie $\displaystyle S$ potraja się)
5. Jeśli słowo na taśmie $\displaystyle C$ jest krótsze niż słowo na taśmie $\displaystyle I$, wykonaj ponownie krok 4.
6. W tym momencie na taśmie $\displaystyle S$ zostało zaznaczone $\displaystyle 3^{n}$ komórek.

Zamieniamy wypisane symbole na $\displaystyle 1$ (zapominamy o symulacji taśm), wracamy nad pierwszy symbol (przed lewym markerem) i przechodzimy do konfiguracji końcowej $\displaystyle s_{1}\in S_{F}$.

Po zakończeniu cyklu doszliśmy do konfiguracji $\displaystyle \sharp s_{1}1^{3^{n}}\sharp$, co było wymagane w definicji konstruowalności pamięciowej.

Ćwiczenie 4

Skonstruuj maszynę Turinga rozpoznającą język zadany gramatyką:

$\displaystyle S\rightarrow aTb|b\quad ,\quad T\rightarrow Ta|1.$

Wskazówka

Zacznij od wypisania języka opisanego przez daną gramatykę.

Rozwiązanie

Analizując postać gramatyki, dochodzimy do wniosku, że zadana maszyna ma rozpoznawać język postaci:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{a^n b\: :\; n\geqslant 0\right\}. }

Jest to język regularny, więc rozpoznawany przez automat skończenie stanowy. Zatem do akceptacji tego języka wystarczy, aby maszyna przeszła taśmę z lewej strony do prawej według zasad:

1. Jeśli czytasz symbol $\displaystyle a$, wypisz $\displaystyle a$ i przejdź w prawo, powtarzając ten krok. Jeśli czytasz $\displaystyle b$, przejdź w prawo i wykonaj krok następny.
2. Jeśli jesteś na ograniczniku, to akceptuj, inaczej odrzuć.

Ćwiczenie 5

Przedstaw ideę działania maszyny Turinga rozpoznającej język

$\displaystyle L=\left\{a^{n}b^{2n}c^{3n}\;:\;n>1\right\}.$

Wskazówka

Wykorzystaj kilka taśm oraz konstruowalność pamięciową.

Rozwiązanie

Idea działania poszukiwanej maszyny (czterotaśmowej) jest następująca:

1. Sprawdź czy słowo wjeściowe $\displaystyle w$ zawiera jako pierwszy symbol $\displaystyle a$. Jeśli nie, odrzuć.
2. Skopiuj najdłuższy prefiks słowa wejściowego $\displaystyle w$ postaci $\displaystyle a^{k}$ na taśmę nr 2.
3. Korzystając z konstruowalności pamięciowej funkcji $\displaystyle 2k$ oraz $\displaystyle 3k$ wypisz słowo $\displaystyle b^{2k}$ na taśmie nr $\displaystyle 3$ oraz słowo $\displaystyle c^{3k}$ na taśmie nr $\displaystyle 4$.
4. Dopisz słowo z taśmy nr $\displaystyle 3$ i $\displaystyle 4$ do słowa na taśmie nr $\displaystyle 2$. W tym momencie na taśmie nr $\displaystyle 2$ znajduje się słowo $\displaystyle a^{k}b^{2k}c^{3k}$.
5. Porównaj słowo z taśmy nr $\displaystyle 2$ ze słowem $\displaystyle w$. Jeśli są identyczne, to akceptuj.

Ćwiczenie 6

W trakcie wykładu rozważaliśmy zamkniętość klas języków w klasyfikacji Chomsky'ego ze względu na różne działania. Podaj uzasadnienie (ideę konstrukcji) następującego faktu:

Dla dowolnych maszyn Turinga $\displaystyle TM_{1}$, $\displaystyle TM_{2}$ istnieje maszyna $\displaystyle {\mathcal {M}}$ o własności:

1. $\displaystyle L({\mathcal {M}})=L(TM_{1})\cup L(TM_{2}),$
2. $\displaystyle L({\mathcal {M}})=L(TM_{1})\cap L(TM_{2}).$

Wskazówka

Wykonaj odpowiednią symulację maszyn $\displaystyle TM_{1}$ oraz $\displaystyle TM_{2}$.

Rozwiązanie

(Ad. 1) Konstruujemy maszynę dwutaśmową, która działa według zasady:

1. Kopiuj słowo wejściowe na taśmę nr 2. Symuluj kolejno jeden krok czasowy $\displaystyle TM_{1}$ na taśmie $\displaystyle 1$ i jeden krok $\displaystyle TM_{2}$ na taśmie $\displaystyle 2$.
2. Jeśli któraś z maszyn zaakceptowała, to akceptuj.

(Ad. 2) Konstrukcja jest niemalże identyczna. Jedynie w kroku (2) akceptujemy, gdy obie maszyny zaakceptowały. Ponieważ może to się stać w różnych krokach czasowych, w momencie, gdy jedna z maszyn zaakceptuje, kończymy jej symulację i symulujemy tylko drugą, aż do momentu, gdy zaakceptuje (o ile to nastąpi).

Ćwiczenie 7

Czy któraś z poniższych list słów ma własność Posta?

1. $\displaystyle (u_{1},v_{1})=\left[{\begin{array}{c}a^{2}\\a^{2}b\end{array}}\right]\;,\;(u_{2},v_{2})=\left[{\begin{array}{c}b^{2}\\ba\end{array}}\right]\;,\;(u_{3},v_{3})=\left[{\begin{array}{c}ab^{2}\\b\end{array}}\right]$
2. $\displaystyle (u_{1},v_{1})=\left[{\begin{array}{c}a\\b^{2}\end{array}}\right]\;,\;(u_{2},v_{2})=\left[{\begin{array}{c}a^{2}\\b\end{array}}\right]$
3. $\displaystyle (u_{1},v_{1})=\left[{\begin{array}{c}ba\\abab\end{array}}\right],(u_{2},v_{2})=\left[{\begin{array}{c}b\\a\end{array}}\right],(u_{3},v_{3})=\left[{\begin{array}{c}aba\\b\end{array}}\right],(u_{4},v_{4})=\left[{\begin{array}{c}aa\\a\end{array}}\right]$

Rozwiązanie

(Ad. 1) Rozważmy ciąg indeksów $\displaystyle (1,2,1,3)$. Otrzymujemy:

$\displaystyle \left[{\begin{array}{c}a^{2}\\a^{2}b\end{array}}\right]\left[{\begin{array}{c}b^{2}\\ba\end{array}}\right]\left[{\begin{array}{c}a^{2}\\a^{2}b\end{array}}\right]\left[{\begin{array}{c}ab^{2}\\b\end{array}}\right]=\left[{\begin{array}{c}a^{2}b^{2}a^{2}ab^{2}\\a^{2}bbaa^{2}bb\end{array}}\right]=\left[{\begin{array}{c}a^{2}b^{2}a^{3}b^{2}\\a^{2}b^{2}a^{3}b^{2}\end{array}}\right]$

Zatem własność Posta zachodzi dla tej listy.

(Ad. 2) Dany ciąg nie ma własności Posta. Bez względu na kolejność indeksów pierwsze ze słów zawsze jest postaci $\displaystyle a^{k}$, a drugie $\displaystyle b^{j}$, dla pewnych $\displaystyle k,j>0$. Ale zawsze $\displaystyle a^{k}\neq b^{j}$, czyli własność Posta nie może zachodzić.

(Ad. 3) Rozważmy ciąg indeksów $\displaystyle (4,2,3,2,3,1,1)$. Zestawiając zadane pary słów w tej kolejności, otrzymujemy:

$\displaystyle \left[{\begin{array}{c}aa\\a\end{array}}\right]\left[{\begin{array}{c}ba\\abab\end{array}}\right]\left[{\begin{array}{c}ba\\abab\end{array}}\right]\left[{\begin{array}{c}b\\a\end{array}}\right]\left[{\begin{array}{c}aba\\b\end{array}}\right]\left[{\begin{array}{c}b\\a\end{array}}\right]\left[{\begin{array}{c}aa\\a\end{array}}\right]$ $\displaystyle =\left[{\begin{array}{c}aabababababaa\\aabababababaa\end{array}}\right]$

W ten sposób wykazaliśmy, że własność Posta zachodzi.

Ćwiczenie 8

W definicji problemu Posta zakłada się, że alfabet $\displaystyle {\mathcal {A}}$ zawiera co najmniej dwa elementy. Wykaż, że gdy to założenie nie jest spełnione (tzn. $\displaystyle {\mathcal {A}}=\left\{1\right\}$) problem Posta jest problemem rozstrzygalnym.

Wskazówka

Rozważ dwa przypadki, zależnie od tego, czy lista zawiera tylko pary słów postaci $\displaystyle (a^{k},a^{j})$, gdzie $\displaystyle k>j$ (lub tylko $\displaystyle k<j$), czy też jeszcze jakieś inne pary słów.

Rozwiązanie

Rozważmy listę par słów $\displaystyle (u_{1},v_{1}),\dots ,(u_{n},v_{n})$ nad alfabetem $\displaystyle {\mathcal {A}}$. Przedstawimy algorytm sprawdzający, czy lista ma własność Posta:

1. Jeśli lista zawiera parę $\displaystyle (1^{k},1^{k})$, to mamy własność Posta.
2. Jeśli jedyne pary to takie, w których $\displaystyle (u_{i},v_{i})=(1^{k_{i}},1^{l_{i}})$ oraz $\displaystyle k_{i}>l_{i}$ (lub $\displaystyle k_{i}<l_{i}$), dla

$\displaystyle i=1,\dots ,n$, to własność Posta nie jest spełniona (słowo dane przez katenację dowolnych $\displaystyle u_{i}$ zawsze zawiera więcej (odp. mniej) symboli niż odpowiadająca mu katenacja słow $\displaystyle v_{i}$ )

1. W ostatnim przypadku istnieją indeksy $\displaystyle i,j$ takie, że

$\displaystyle (u_{i},v_{i})=(1^{k},1^{l})\quad ,\quad (u_{j},v_{j})=(1^{p},1^{q}),$

przy czym $\displaystyle k<l$ i $\displaystyle p>q$. W tej sytuacji zachodzi własność Posta. Uzasadnienie jest następujące. Biorąc ciąg:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle \begin{array} {c c c} (\underbrace{i\;,\; \dots\;,\;i}&,&\underbrace{j\;,\;\dots\;,\;j})\\ {\displaystyle p-q \mbox{ razy}\displaystyle && {\displaystyle l-k \mbox{ razy}\displaystyle \end{array}}

otrzymujemy słowa:

$\displaystyle \left[{\begin{array}{c}u_{1}\\v_{1}\end{array}}\right]^{p-q}\left[{\begin{array}{c}u_{2}\\v_{2}\end{array}}\right]^{l-k}=\left[{\begin{array}{c}1^{k}\\1^{l}\end{array}}\right]^{p-q}\left[{\begin{array}{c}1^{p}\\1^{1}\end{array}}\right]^{l-k}=\left[{\begin{array}{c}1^{k(p-q)}\\1^{l(p-q)}\end{array}}\right]\left[{\begin{array}{c}1^{p(l-k)}\\1^{q(l-k)}\end{array}}\right]$ $\displaystyle =\left[{\begin{array}{c}1^{kp-kq+pl-pk}\\1^{lp-lq+ql-qk}\end{array}}\right]=\left[{\begin{array}{c}1^{lp-kq}\\1^{lp-kq}\end{array}}\right]$

Dla danej listy, można rostrzygnąć w czasie wielomianowym, który z przypadków (1), (2), (3) zachodzi. Otrzymaliśmy rozstrzygalność problemu Posta dla tej sytuacji.

ZADANIA DOMOWE

Ćwiczenie 9

Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga $\displaystyle {\mathcal {MT}}$ akceptującej język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}. }

Zmodyfikuj, ewentualnie, tę konstrukcję $\displaystyle {\mathcal {MT}}$, aby udowodnić $\displaystyle L_{1}\in$ P .

Ćwiczenie 10

Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga $\displaystyle {\mathcal {NMT}}$ akceptującej język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_2=\left\{w_1 w_1 w_2 w_2 \dots w_n w_n \: : \: w_i \in \left\{\circ,\bullet\right\}^+, n>0 \right\}. }

Zmodyfikuj, ewentualnie, tę konstrukcję $\displaystyle {\mathcal {NMT}}$ aby udowodnić, że $\displaystyle L_{2}\in$ NP .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego $\displaystyle w$ przeprowadź weryfikację w trzech etapach: konstrukcja słów $\displaystyle w_{1},\dots ,w_{n}$, gdzie $\displaystyle n<|w|$ (wyrocznia), sklejanie, weryfikacja, czy $\displaystyle w=w_{1}w_{1}w_{2}w_{2}\dots w_{n}w_{n}$.

Ćwiczenie 11

Uzasadnij, że jeśli funkcja $\displaystyle s(n)$ jest konstruowalna pamięciowo, to obliczenie $\displaystyle d_{1}\mapsto ^{*}d_{2}$ z definicji konstruowalności pamięciowej (tzn. $\displaystyle d_{1}=\sharp s_{0}1^{n}\sharp$, $\displaystyle d_{2}=\sharp s_{1}1^{s(n)}w\sharp$) następuje w co najwyżej $\displaystyle c2^{s(n)}$ krokach, gdzie $\displaystyle c$ jest pewną stałą niezależną od $\displaystyle n$.
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 12

Uzasadnij, że funkcja $\displaystyle n^{3}$ jest konstruowalna pamięciowo.

Ćwiczenie 13

Skonstruuj maszynę Turinga akceptującą słowo $\displaystyle u=1^{n}$ w dokładnie $\displaystyle n^{2}$ krokach. Jak zmodyfikować konstrukcję maszyny, aby akceptowała słowo $\displaystyle u$ dokładnie w $\displaystyle 2^{n}$ krokach?

Ćwiczenie 14

Wypisz dokładnie wszystkie elementy składowe maszyn Turinga rozpoznających języki zadane gramatykami:

1. $\displaystyle S\rightarrow AbC$ , $\displaystyle A\rightarrow aAb|1$, $\displaystyle C\rightarrow bCc|1$
2. $\displaystyle S\rightarrow ABACA\quad ,\quad A\rightarrow Aa|a\quad ,\quad B\rightarrow bb|b\quad ,\quad C\rightarrow c|1.$

Ćwiczenie 15

Wykaż (podając ideę kontrukcji), że dla maszyn Turinga $\displaystyle TM_{1}$, $\displaystyle TM_{2}$ istnieje maszyna Turinga $\displaystyle {\mathcal {M}}$ rozpoznająca język:

$\displaystyle L({\mathcal {M}})=\left\{uv\;:\;u\in L(TM_{1}),v\in L(TM_{2})\right\}.$

Ćwiczenie 16

Czy któraś z poniższych list słów ma własność Posta?

1. $\displaystyle (u_{1},v_{1})=\left[{\begin{array}{c}a\\a^{2}b\end{array}}\right]\;,\;(u_{2},v_{2})=\left[{\begin{array}{c}ba^{2}\\a^{2}\end{array}}\right]$
2. $\displaystyle (u_{1},v_{1})=\left[{\begin{array}{c}a^{b}\\a\end{array}}\right]\;,\;(u_{2},v_{2})=\left[{\begin{array}{c}a\\ba^{2}\end{array}}\right]$
3. $\displaystyle (u_{1},v_{1})=\left[{\begin{array}{c}aaa\\a\end{array}}\right],(u_{2},v_{2})=\left[{\begin{array}{c}b\\ba\end{array}}\right],(u_{3},v_{3})=\left[{\begin{array}{c}bb\\b\end{array}}\right],(u_{4},v_{4})=\left[{\begin{array}{c}ba\\ab\end{array}}\right]$

Ćwiczenie 17

Udowodnij Twierdzenie 2.1 z wykładu:

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