Języki, automaty i obliczenia/Ćwiczenia 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga

Ćwiczenia 12

Ćwiczenie 1

Rozważmy maszynę Turinga $T{M}_2$ z wykładu (Przykład 1.2) akceptującą język palindromów, czyli:

$L=\{w\overleftarrow{w}:::w\in {\{0,1\}}^{*}\}$

Sprawdź, że:

1. $101101\in L(T{M}_2)$

oraz że

1. $1010101\in ̸L(T{M}_2)$.

Wskazówka

Aby wykonać (1), rozpocznij od konfiguracji $\mathrm{♯}:s_{0}1:01101\mathrm{♯}$, a następnie wykonuj przejścia, zgodnie z diagramem przejść maszyny $T{M}_2$ z wykładu.

Rozwiązanie

(Ad. 1) Wykonujemy symulację maszyny $T{M}_2$ na pierwszym ze słów:

$\begin{array}{cccccccc}& \mathrm{♯}:s_{0}1:01101\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:r_{1}0:1101\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}0:{r_1}^{\prime }1:101\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}01:{r_1}^{\prime }1:01\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♯}011:{r_1}^{\prime }0:1\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}0110:{r_1}^{\prime }1:\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}01101:{r_1}^{\prime }\mathrm{♯}& \mapsto & \mathrm{♯}0110:q_{1}1:\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♯}011:l0:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}01:l1:0\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}0:l1:10\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:l0:110\mathrm{♯}\mathrm{♯}\\ \mapsto & \mathrm{♯}:l\mathrm{♯}:0110\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:s_{0}0:110\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:r_{0}1:10\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}1:{r_0}^{\prime }1:0\mathrm{♯}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}11:{r_0}^{\prime }0:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}110:{r_0}^{\prime }\mathrm{♯}:\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}11:q_{0}0:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}1:l1:\mathrm{♯}\mathrm{♯}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:l1:1\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:l\mathrm{♯}:11\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:s_{0}1:1\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:r_{1}1:\mathrm{♯}\mathrm{♯}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}1:{r_1}^{\prime }\mathrm{♯}:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:q_{1}1:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:l\mathrm{♯}:\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:s_0\mathrm{♯}:\mathrm{♯}\mathrm{♯}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:s_A\mathrm{♯}:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \circlearrowleft & \end{array}$

Wykazaliśmy, że $\mathrm{♯}:s_{0}1:01101\mathrm{♯}{\mapsto }^{*}\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:s_A\mathrm{♯}:\mathrm{♯}\mathrm{♯}\mathrm{♯}$. Stan $s_A\in S_F$, zatem wprost z definicji $101101\in L(T{M}_2)$.

(Ad. 2) Wykonujemy identyczną symulację na drugim ze słów:

$\begin{array}{ccccccccc}& \mathrm{♯}:s_{0}1:010101\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:r_{1}0:10101\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}0:{r_1}^{\prime }1:0101\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}01:{r_1}^{\prime }0:101\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}010:{r_1}^{\prime }1:01\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}0101:{r_1}^{\prime }0:1\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}01010:{r_1}^{\prime }1:\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}010101:{r_1}^{\prime }\mathrm{♯}& \\ \mapsto & \mathrm{♯}01010:q_{1}1:\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}0101:l0:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}010:l1:0\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}01:l0:10\mathrm{♯}\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}0:l1:010\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:l0:1010\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}:l\mathrm{♯}:01010\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:s_{0}0:1010\mathrm{♯}\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:r_{0}1:010\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}1:{r_0}^{\prime }0:10\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}10:{r_0}^{\prime }1:0\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}101:{r_0}^{\prime }0:\mathrm{♯}\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}1010:{r_0}^{\prime }\mathrm{♯}:\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}101:q_{0}0:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}10:l1:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:1l0:1\mathrm{♯}\mathrm{♯}\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:l1:01\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}:l\mathrm{♯}:101\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:s_{0}1:01\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:r_{1}0:1\mathrm{♯}\mathrm{♯}\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}0:r_{1}1:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}01:{r_1}^{\prime }\mathrm{♯}:\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}0:q_{1}1:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:l0:\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}& \\ \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}:l\mathrm{♯}:0\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:s_{0}0:\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:r_0\mathrm{♯}:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}\mathrm{♯}:s_R\mathrm{♯}:\mathrm{♯}\mathrm{♯}\mathrm{♯}& \circlearrowleft \\ \end{array}$

Na ostatniej otrzymanej konfiguracji maszyna się zatrzymuje (następne konfiguracje są identyczne). Zatem konfiguracja początkowa $\mathrm{♯}:s_{0}1:010101\mathrm{♯}$ prowadzić może poprzez relację ${\mapsto }^{*}$ tylko do konfiguracji (obliczeń wykonanych) wypisanych powyżej. Żadna z otrzymanych konfiguracji pośrednich nie zawiera stanu ze zbioru $S_F$. To z kolei oznacza, że $1010101\in ̸L(T{M}_2)$.

Ćwiczenie 2

Niech będzie dany alfabet ${\mathrm{\Sigma }}_I=\{0,1,\mathrm{♣}\}$. Zaprojektuj maszynę Turinga akceptująca język postaci:

$L=\{u\mathrm{♣}w:::u,w\in {\{0,1\}}^{*}\}$

Zaprojektuj maszynę Turinga ${ℳ}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$, która akceptuje język $L$. Następnie:

1. Wypisz elementy składowe maszyny ${ℳ}$, tzn. zbiory ${\mathrm{\Sigma }}_T,S,S_F$ oraz funkcję przejścia $f$ (zapewnij, aby $s_0\in S$).
2. Wykonaj symulację maszyny ${ℳ}$ na słowie $w_1=1100\mathrm{♣}11$,
3. na słowie $w_2=\mathrm{♣}01\mathrm{♣}$,
4. oraz na słowie $w_3=0000110$.

Wskazówka

Projektowana maszyna może działać według schematu:

1. Przejdź słowo wejściowe od lewego do prawego ogranicznika.
2. Jeśli napotkasz symbol $\mathrm{♣}$, oznacz to w stanach maszyny.
3. Jeśli napotkasz symbol $\mathrm{♣}$ ponownie, to odrzuć.
4. Gdy dotarłeś do prawego ogranicznika i nie napotkałeś $\mathrm{♣}$, to odrzuć; w przeciwnym przypadku akceptuj.

Rozwiązanie

(Ad. 1) Wypiszemy maszynę ${ℳ}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$ działającą według zaproponowanego we wskazówce schematu. Zbiór ${\mathrm{\Sigma }}_I$ oraz stan początkowy $s_0$ zostały narzucone treścią zadania. Oznaczamy kolejno:

${\mathrm{\Sigma }}_T=\{0,1,\mathrm{♣},\mathrm{♯}\},S=\{s_0,s_1,s_R,s_A\},S_F=\left\{s_A\right\}$

oraz definiujemy funkcję przejścia według tabeli:

$(s_0,0)\mapsto (s_0,0,1)$	$(s_0,1)\mapsto (s_0,1,1)$	$(s_0,\mathrm{♣})\mapsto (s_1,\mathrm{♣},1)$	$(s_0,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)$
$(s_1,0)\mapsto (s_1,0,1)$	$(s_1,1)\mapsto (s_1,1,1)$	$(s_1,\mathrm{♣})\mapsto (s_R,\mathrm{♣},0)$	$(s_1,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)$
		$(s_R,\mathrm{♣})\mapsto (s_R,\mathrm{♣},0)$	$(s_R,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)$
			$(s_A,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)$

Wykonujemy kolejno symulację maszyny Turinga ${ℳ}$ na słowach:
(Ad. 2) $w_1=1100\mathrm{♣}11$

$\begin{array}{cccccccc}& \mathrm{♯}{s}_{0}1100\mathrm{♣}11\mathrm{♯}& \mapsto & \mathrm{♯}1s_{0}100\mathrm{♣}11\mathrm{♯}& \mapsto & \mathrm{♯}11s_{0}00\mathrm{♣}11\mathrm{♯}& \mapsto & \mathrm{♯}110s_{0}0\mathrm{♣}11\mathrm{♯}\\ \mapsto & \mathrm{♯}1100s_0\mathrm{♣}11\mathrm{♯}& \mapsto & \mathrm{♯}1100\mathrm{♣}{s}_{1}11\mathrm{♯}& \mapsto & \mathrm{♯}1100\mathrm{♣}1s_{1}1\mathrm{♯}& \mapsto & \mathrm{♯}1100\mathrm{♣}11s_1\mathrm{♯}\\ \mapsto & \mathrm{♯}1100\mathrm{♣}11s_A\mathrm{♯}& \circlearrowleft \end{array}$

Konfiguracja końcowa jest akceptująca, zatem rzeczywiście $w_1\in L({ℳ})$.

(Ad. 3) $w_2=\mathrm{♣}01\mathrm{♣}$

$\begin{array}{cccccccc}& \mathrm{♯}{s}_0\mathrm{♣}01\mathrm{♣}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_{1}01\mathrm{♣}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}0s_{1}1\mathrm{♣}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}01s_1\mathrm{♣}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♣}01s_R\mathrm{♣}\mathrm{♯}& \circlearrowleft \end{array}$

Żadna z otrzymanych konfiguracji nie była akceptująca, zatem $w_2\in ̸L({ℳ})$.

(Ad. 4) $w_3=0000110$

$\begin{array}{cccccccc}& \mathrm{♯}{s}_{0}0000110\mathrm{♯}& \mapsto & \mathrm{♯}0s_{0}000110\mathrm{♯}& \mapsto & \mathrm{♯}00s_{0}00110\mathrm{♯}& \mapsto & \mathrm{♯}000s_{0}0110\mathrm{♯}\\ \mapsto & \mathrm{♯}0000s_{0}110\mathrm{♯}& \mapsto & \mathrm{♯}00001s_{0}10\mathrm{♯}& \mapsto & \mathrm{♯}000011s_{0}0\mathrm{♯}& \mapsto & \mathrm{♯}0000110s_0\mathrm{♯}\\ \mapsto & \mathrm{♯}0000110s_R\mathrm{♯}& \circlearrowleft \end{array}$

Tak jak w poprzednim przypadku $w_3\in ̸L({ℳ})$.

Ćwiczenie 3

W trakcie wykładu rozważaliśmy język

$L=\{3^k:::k=i\cdot j\text{ dla pewnych }i,j>1\},$

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

Uzasadnij, że także $L\in$ P ${\displaystyle }$.

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 4

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 5

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ę. W przeciwnym wypadku, 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$ wzrasta trzykrotnie)
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.

Zadania domowe

Ćwiczenie 6

Skonstruuj maszynę Turinga ${ℳ}{𝒯}$ akceptującą język:

$L_1=\{www:::w\in {\{\circ ,\bullet ,\star \}}^{*}\}$

Ćwiczenie 7

Uzasadnij, że język

$L_2=\{w_1{w}_1{w}_2{w}_2\dots w_n{w}_n:::w_i\in {\{\circ ,\bullet \}}^{+},n>0\}$

jest rozpoznawany przez pewną niedeterministyczna maszynę Turinga ${𝒩}{ℳ}{𝒯}$.

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