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

Ćwiczenia 14

Ćwiczenie 1

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:

$\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 2

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 3

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 4

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 5

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:

${\begin{array}{c c c}(\underbrace {i\;,\;\dots \;,\;i} _{p-q{\text{ razy}}}&,&\underbrace {j\;,\;\dots \;,\;j} _{l-k{\text{ razy}}})\\\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 6

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 7

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 8

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 9

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 10

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