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

Ć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 $i,j>1\},$

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

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

Wskazówka

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

Rozwiązanie

Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie $k^2$ (wielomianową ilość) mnożeń. Sama weryfikacja zależności $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 $1$ jest tylko do odczytu. Mamy na niej słowo $3^k$.
2. Rozpocznij od zapisania słowa $11$ na taśmie nr $2$ i słowa $22$ na taśmie nr $3$.
3. Przepisz słowa na taśmę nr $4$ według kolejności taśm $2,3,1$.
4. Sprawdź na taśmie nr $4$, czy $k=i\cdot j$. Jeśli tak, to akceptuj. Inaczej krok następny.
5. Dopisz symbol $1$ na taśmie nr $2$. Gdy powstało słowo dłuższe niż $k$, dopisz symbol $2$ na taśmie nr $3$, a słowo na taśmie nr $2$ usuń i zapisz na niej słowo $11$.
6. Jeśli słowo na taśmie nr $3$ jest dłuższe niż $k$, to odrzuć. W przeciwnym przypadku przejdź do kroku 3.

Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr $2$ (licznik 1) i $3$ (licznik 2) jako liczniki, a na taśmie $4$ wykonuj symulacje. Zacznij od stanu liczników na $2$ i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej $2$) i zwiększ licznik $2$. Gdy on także się przepełni, to iloczyn stanów liczników przekracza $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 $n$). Dla małych $n$ możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. Zatem $L\in$ P .

Ćwiczenie 2

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

Wskazówka

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

Rozwiązanie

Bierzemy maszynę $M{T}_4$ z wykładu konstruującą funkcję $2n$. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez $I$ oraz $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ę ${ℳ}$ według schematu:

1. Jeśli słowo wejściowe jest puste, to stop.
2. Jeśli słowo wejściowe jest inne niż $1^n$, to odrzuć.
3. Przepisz słowo wejściowe tak aby znajdowało się na taśmie $I$, a taśma $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ę $S$.
5. Symulujemy maszynę $M{T}_4$ na taśmie $S$.
6. Dopisujemy do taśmy $S$ słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie $3n$ komórek taśmy.
7. Zamieniamy symbole na $1$ (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy

do konfiguracji końcowej $s_1\in S_F$.

Po zakończeniu cyklu doszliśmy do konfiguracji $\mathrm{♯}{s}_1{1}^{3n}\mathrm{♯}$, co było wymagane w definicji.

Ćwiczenie 3

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

Wskazówka

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

Rozwiązanie

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

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

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

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

Ćwiczenie 4

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 5

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

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 8

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 9

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 10

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 11

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 12

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

Ćwiczenie 13

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 14

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 15

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 16

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