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

Taśma nr $1$ jest tylko do odczytu. Mamy na niej słowo $3^{k}$ .
Rozpocznij od zapisania słowa $11$ na taśmie nr $2$ i słowa $22$ na taśmie nr $3$
Przepisz słowa na taśmę nr $4$ według kolejności taśm $2, 3, 1$ .
Sprawdź na taśmie nr $4$ czy $k = i \cdot j$ . Jeśli tak to akceptuj. Inaczej krok następny.
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$ .
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) = 3 n$ jest konstruowalna pamięciowo.

Wskazówka

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

Rozwiązanie

Bierzemy maszynę $M T_{4}$ z wykładu konstruującą funkcję $2 n$ . 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

Jeśli słowo wejściowe jest puste to stop.
Jeśli słowo wejściowe jest inne niż $1^{n}$ to odrzuć.
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).

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

Rozwiązanie

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

Jeśli słowo początkowe jest puste wypisz $1$ i zatrzymaj się. Inaczej wykonaj następny krok.
Jeśli słowo wejściowe jest inne niż $1^{n}$ to odrzuć.
Na taśmie $I$ wypisz słowo wejściowe, na taśmach $C$ i $S$ wypisz słowo $1$ .
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ę)

Jeśli słowo na taśmie $C$ jest krótsze niż słowo na taśmie $I$ wykonaj ponownie krok Uzupelnic step4|.
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 $♯ s_{1} 1^{3^{n}} ♯$ co było wymagane w definicji konstruowalności pamięciowej.

Ćwiczenie

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

S \to a T b | b, T \to T a | 1

Wskazówka

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:

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.

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

Ćwiczenie

Przedstaw ideę działania maszyny Turinga rozpoznającej język

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

Wskazówka

Rozwiązanie

Idea działania poszukiwanej maszyny (cztero taśmowej) jest następująca:

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

odrzuć.

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

taśmę nr dwa.

Korzystając z konstruowalności pamięciowej funkcji $2 k$ oraz

$3 k$ wypisz słowo $b^{2 k}$ na taśmie nr $3$ oraz słowo $c^{3 k}$ na taśmie nr $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^{2 k} c^{3 k}$ .

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:

$L (ℳ) = L (T M_{1}) \cup L (T M_{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:

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

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?

$(u_{1}, v_{1}) = [\begin{array}{c} a^{2} \\ a^{2} b \end{array}], (u_{2}, v_{2}) = [\begin{array}{c} b^{2} \\ b a \end{array}], (u_{3}, v_{3}) = [\begin{array}{c} a b^{2} \\ b \end{array}]$
$(u_{1}, v_{1}) = [\begin{array}{c} a \\ b^{2} \end{array}], (u_{2}, v_{2}) = [\begin{array}{c} a^{2} \\ b \end{array}]$
$(u_{1}, v_{1}) = [\begin{array}{c} b a \\ a b a b \end{array}], (u_{2}, v_{2}) = [\begin{array}{c} b \\ a \end{array}], (u_{3}, v_{3}) = [\begin{array}{c} a b a \\ b \end{array}], (u_{4}, v_{4}) = [\begin{array}{c} a a \\ a \end{array}]$

Rozwiązanie

(Ad. 1) Rozważmy ciąg indeksów $(1, 2, 1, 3)$ . Otrzymujemy:

[\begin{array}{c} a^{2} \\ a^{2} b \end{array}] [\begin{array}{c} b^{2} \\ b a \end{array}] [\begin{array}{c} a^{2} \\ a^{2} b \end{array}] [\begin{array}{c} a b^{2} \\ b \end{array}] = [\begin{array}{c} a^{2} b^{2} a^{2} a b^{2} \\ a^{2} b b a a^{2} b b \end{array}] = [\begin{array}{c} a^{2} b^{2} a^{3} b^{2} \\ a^{2} b^{2} a^{3} b^{2} \end{array}]

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} \neq 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:

[\begin{array}{c} a a \\ a \end{array}] [\begin{array}{c} b a \\ a b a b \end{array}] [\begin{array}{c} b a \\ a b a b \end{array}] [\begin{array}{c} b \\ a \end{array}] [\begin{array}{c} a b a \\ b \end{array}] [\begin{array}{c} b \\ a \end{array}] [\begin{array}{c} a a \\ a \end{array}]

= [\begin{array}{c} a a b a b a b a b a b a a \\ a a b a b a b a b a b a a \end{array}]

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. $𝒜 = {1}$ ) 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.

Jeśli lista zawiera parę $(1^{k}, 1^{k})$ to mamy własność Posta.
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}$ )

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:

{[\begin{array}{c} u_{1} \\ v_{1} \end{array}]}^{p - q} {[\begin{array}{c} u_{2} \\ v_{2} \end{array}]}^{l - k} = {[\begin{array}{c} 1^{k} \\ 1^{l} \end{array}]}^{p - q} {[\begin{array}{c} 1^{p} \\ 1^{1} \end{array}]}^{l - k} = [\begin{array}{c} 1^{k (p - q)} \\ 1^{l (p - q)} \end{array}] [\begin{array}{c} 1^{p (l - k)} \\ 1^{q (l - k)} \end{array}]

= [\begin{array}{c} 1^{k p - k q + p l - p k} \\ 1^{l p - l q + q l - q k} \end{array}] = [\begin{array}{c} 1^{l p - k q} \\ 1^{l p - k q} \end{array}]

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} = ♯ s_{0} 1^{n} ♯$ , $d_{2} = ♯ s_{1} 1^{s (n)} w ♯$ ) 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:

$S \to A b C$ , $A \to a A b | ε$ , $C \to b C c | ε$
$S \to A B A C A, A \to A a | a, B \to b b | b, C \to c | ε$

Ćwiczenie

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

L (ℳ) = {u v : 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?

$(u_{1}, v_{1}) = [\begin{array}{c} a \\ a^{2} b \end{array}], (u_{2}, v_{2}) = [\begin{array}{c} b a^{2} \\ a^{2} \end{array}]$
$(u_{1}, v_{1}) = [\begin{array}{c} a^{b} \\ a \end{array}], (u_{2}, v_{2}) = [\begin{array}{c} a \\ b a^{2} \end{array}]$
$(u_{1}, v_{1}) = [\begin{array}{c} a a a \\ a \end{array}], (u_{2}, v_{2}) = [\begin{array}{c} b \\ b a \end{array}] (u_{3}, v_{3}) = [\begin{array}{c} b b \\ b \end{array}] (u_{4}, v_{4}) = [\begin{array}{c} b a \\ a b \end{array}]$

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

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

ĆWICZENIA 13

Zadania domowe

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia