Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.

Ćwiczenia 13

Ćwiczenie 1

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

$S\to aTb|b,T\to 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 $a$, wypisz $a$ i przejdź w prawo, powtarzając ten krok. Jeśli czytasz $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

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

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 $w$ zawiera jako pierwszy symbol $a$. Jeśli nie, odrzuć.
2. Skopiuj najdłuższy prefiks słowa wejściowego $w$ postaci $a^k$ na taśmę nr 2.
3. Korzystając z konstruowalności pamięciowej funkcji $2k$ oraz $3k$ wypisz słowo $b^{2k}$ na taśmie nr $3$ oraz słowo $c^{3k}$ na taśmie nr $4$.
4. Dopisz słowo z taśmy nr $3$ i $4$ do słowa na taśmie nr $2$. W tym momencie na taśmie nr $2$ znajduje się słowo $a^k{b}^{2k}{c}^{3k}$.
5. Porównaj słowo z taśmy nr $2$ ze słowem $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 $T{M}_1$, $T{M}_2$ istnieje maszyna ${ℳ}$ o własności:

1. $L({ℳ})=L(T{M}_1)\cup L(T{M}_2),$
2. $L({ℳ})=L(T{M}_1)\cap L(T{M}_2).$

Wskazówka

Wykonaj odpowiednią symulację maszyn $T{M}_1$ oraz $T{M}_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 $T{M}_1$ na taśmie $1$ i jeden krok $T{M}_2$ na taśmie $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. $(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}a{b}^2\\ b\end{array}\right]$
2. $(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. $(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 $(1,2,1,3)$. Otrzymujemy:

$\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}a{b}^2\\ b\end{array}\right]=\left[\begin{array}{c}{a}^2{b}^2{a}^{2}a{b}^2\\ a^{2}bba{a}^{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 $a^k$, a drugie $b^j$, dla pewnych $k,j>0$. Ale zawsze $a^k\ne b^j$, czyli własność Posta nie może zachodzić.

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

$\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]$ $=\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 ${𝒜}$ zawiera co najmniej dwa elementy. Wykaż, że gdy to założenie nie jest spełnione (tzn. ${𝒜}=\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 $(a^k,a^j)$, gdzie $k>j$ (lub tylko $k<j$), czy też jeszcze jakieś inne pary słów.

Rozwiązanie

Rozważmy listę par słów $(u_1,v_1),\dots ,(u_n,v_n)$ nad alfabetem ${𝒜}$. Przedstawimy algorytm sprawdzający, czy lista ma własność Posta:

1. Jeśli lista zawiera parę $(1^k,1^k)$, to mamy własność Posta.
2. Jeśli jedyne pary to takie, w których $(u_i,v_i)=(1^{k_i},1^{l_i})$ oraz $k_i>l_i$ (lub $k_i<l_i$), dla

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

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

$(u_i,v_i)=(1^k,1^l),(u_j,v_j)=(1^p,1^q),$

przy czym $k<l$ i $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:

${\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]$ $=\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

Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga ${ℳ}{𝒯}$ 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ę ${ℳ}{𝒯}$, aby udowodnić $L_1\in$ P .

Ćwiczenie 7

Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga ${𝒩}{ℳ}{𝒯}$ 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ę ${𝒩}{ℳ}{𝒯}$ aby udowodnić, że $L_2\in$ NP .

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

Ćwiczenie 8

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

Ćwiczenie 9

Uzasadnij, że funkcja $n^3$ jest konstruowalna pamięciowo.

Ćwiczenie 10

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

Ćwiczenie 11

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

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

Ćwiczenie 12

Wykaż (podając ideę kontrukcji), że dla maszyn Turinga $T{M}_1$, $T{M}_2$ istnieje maszyna Turinga ${ℳ}$ rozpoznająca język:

$L({ℳ})=\{uv:u\in L(T{M}_1),v\in L(T{M}_2)\}.$

Ćwiczenie 13

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

1. $(u_1,v_1)=\left[\begin{array}{c}a\\ a^{2}b\end{array}\right],(u_2,v_2)=\left[\begin{array}{c}b{a}^2\\ a^2\end{array}\right]$
2. $(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. $(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 14

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 $a$ , jest postaci $v⟶a$ .