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

From Studia Informatyczne

Ć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 b ba a^2 b b \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:

\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 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\\b a^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\\b a \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 .