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

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 2

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

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 3

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

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

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 5

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 (czterotaś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 2.
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 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:

$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ę dwutaś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 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?

$(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 drugie $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 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. $𝒜 = {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})\\ {\displaystyle p-q \mbox{ razy}\displaystyle && {\displaystyle l-k \mbox{ razy}\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 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} = ♯ s_{0} 1^{n} ♯$ , $d_{2} = ♯ s_{1} 1^{s (n)} w ♯$ ) 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:

$S \to A b C$ , $A \to a A b | 1$ , $C \to b C c | 1$
$S \to A B A C A, A \to A a | a, B \to b b | 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 (ℳ) = {u v : 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?

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

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

Ćwiczenia 13

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia