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

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

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

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 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. $𝒜 = {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 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} = ♯ 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 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:

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

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 13

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

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