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

{Złożoność obliczeniowa. Języki maszyn Turinga i typu (0). Rozstrzygalność.}

ĆWICZENIA 13

Ćwiczenie

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle i,j> 1\right\} }

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 cztero-taś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

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 jedna 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 jedno-taś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).

1. Kopiujemy słowo wejściowe na taśmę $S$.
2. Symulujemy maszynę $M{T}_4$ na taśmie $S$.
3. Dopisujemy do taśmy $S$ słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie $3n$ komórek taśmy.
4. 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

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ę)

1. Jeśli słowo na taśmie $C$ jest krótsze niż słowo na taśmie $I$ wykonaj ponownie krok Uzupelnic step4|.
2. 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

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\geq 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.

1. Jeśli jesteś na ograniczniku to akceptuj, inaczej odrzuć.

Ćwiczenie

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 (cztero taśmowej) jest następująca:

1. Sprawdź czy słowo wjeściowe $w$ zawiera jako pierwszy symbol $a$. Jeśli nie

odrzuć.

1. Skopiuj najdłuższy prefiks słowa wejściowego $w$ postaci $a^k$ na

taśmę nr dwa.

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

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

1. Porównaj słowo z taśmy nr $2$ ze słowem $w$. Jeśli są

identyczne to akceptuj.

Ćwiczenie

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ę dwu-taś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$.

1. Jeśli któraś z maszyn zaakceptowała to akceptuj.

(Ad. 2) Konstrukcja jest niemalże identyczne. 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

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

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})\\ } {$p-q$ razy} Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle && } { $l-k$ razy } Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 rostrzygalność problemu Posta dla tej sytuacji.

Zadania domowe

Ćwiczenie

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

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

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ępuję w conajwyżej $c{2}^{s(n)}$ krokach gdzie $c$ jest pewną stałą niezależną od $n$.
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie

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

Ćwiczenie

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

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

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

Ćwiczenie

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

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

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