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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{w \overleftarrow{w} \: : \: w\in \left\{0,1\right\}^*\right\} }

Sprawdź, że

1. $101101\in L(T{M}_2)$ oraz, że
2. $1010101\in ̸L(T{M}_2)$.

Wskazówka

Aby wykonać (1) rozpocznij od konfiguracji Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \sharp \: s_0 1 \: 01101 \sharp} 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:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle \begin{array} {c c c c c c c c} &\sharp \:s_0 1\: 01101 \sharp & \mapsto & \sharp \sharp \: r_1 0\: 1101 \sharp &\mapsto & \sharp \sharp 0 \: r_1' 1\: 101 \sharp &\mapsto & \sharp \sharp 01 \: r_1' 1\: 01 \sharp \\ \mapsto & \sharp \sharp 011 \: r_1' 0\: 1 \sharp & \mapsto & \sharp \sharp 0110 \: r_1' 1 \: \sharp &\mapsto & \sharp \sharp 0110 1 \: r_1' \sharp &\mapsto & \sharp 0110 \: q_1 1\: \sharp \\ \mapsto & \sharp \sharp 011 \: l 0\: \sharp \sharp & \mapsto & \sharp \sharp 01 \: l 1\: 0 \sharp \sharp &\mapsto & \sharp \sharp 0 \: l 1\: 10 \sharp \sharp &\mapsto & \sharp \sharp \: l 0\: 110 \sharp \sharp \\ \mapsto & \sharp \: l \sharp\: 0110 \sharp \sharp & \mapsto & \sharp\sharp \: s_0 0\: 110 \sharp\sharp &\mapsto & \sharp\sharp\sharp \: r_0 1\: 10 \sharp\sharp &\mapsto & \sharp\sharp\sharp 1 \: r_0' 1\: 0 \sharp\sharp \\ \mapsto & \sharp\sharp\sharp 11 \: r_0' 0\: \sharp\sharp & \mapsto & \sharp\sharp\sharp 110 \: r_0' \sharp\: \sharp &\mapsto & \sharp\sharp\sharp 11 \: q_0 0\: \sharp\sharp &\mapsto & \sharp\sharp\sharp 1 \: l 1\: \sharp\sharp\sharp \\ \mapsto & \sharp\sharp\sharp \: l 1\: 1\sharp\sharp\sharp & \mapsto & \sharp\sharp \: l \sharp \: 1 1\sharp\sharp\sharp &\mapsto & \sharp\sharp\sharp \: s_0 1\: 1\sharp\sharp\sharp &\mapsto & \sharp\sharp\sharp\sharp \: r_1 1\: \sharp\sharp\sharp \\ \mapsto & \sharp\sharp\sharp\sharp 1 \: r_1' \sharp\: \sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp \: q_1 1\: \sharp\sharp\sharp &\mapsto & \sharp\sharp\sharp \: l \sharp \: \sharp\sharp\sharp\sharp &\mapsto & \sharp\sharp\sharp\sharp \: s_0 \sharp\: \sharp\sharp\sharp \\ \mapsto & \sharp\sharp\sharp\sharp \: s_A \sharp\: \sharp\sharp\sharp & \circlearrowleft& \end{array} }

Wykazaliśmy, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \sharp \:s_0 1\: 01101 \sharp \mapsto^* \sharp\sharp\sharp\sharp \: s_A \sharp\: \sharp\sharp\sharp} . 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:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle \begin{array} {c c c c c c c c c} &\sharp \:s_0 1\: 010101 \sharp & \mapsto & \sharp \sharp \: r_1 0\: 10101 \sharp &\mapsto & \sharp \sharp 0 \: r_1' 1\: 0101 \sharp &\mapsto & \sharp \sharp 01 \: r_1' 0\: 101 \sharp &\\ \mapsto & \sharp \sharp 010 \: r_1' 1\: 01 \sharp & \mapsto & \sharp \sharp 0101 \: r_1' 0\: 1 \sharp & \mapsto & \sharp \sharp 01010 \: r_1' 1 \: \sharp &\mapsto & \sharp \sharp 01010 1 \: r_1' \sharp &\\ \mapsto & \sharp 01010 \: q_1 1\: \sharp& \mapsto & \sharp \sharp 0101 \: l 0\: \sharp \sharp & \mapsto & \sharp \sharp 010 \: l 1\: 0 \sharp \sharp &\mapsto & \sharp \sharp 0 1\: l 0\: 10 \sharp \sharp &\\ \mapsto & \sharp \sharp 0 \: l 1\: 010 \sharp \sharp& \mapsto & \sharp \sharp \: l 0\: 1010 \sharp \sharp& \mapsto & \sharp \: l \sharp\: 01010 \sharp \sharp & \mapsto & \sharp\sharp \: s_0 0\: 1010 \sharp\sharp &\\ \mapsto & \sharp\sharp\sharp \: r_0 1\: 010 \sharp\sharp & \mapsto & \sharp\sharp\sharp 1 \: r_0' 0\: 10 \sharp\sharp & \mapsto & \sharp\sharp\sharp 10 \: r_0' 1\: 0 \sharp\sharp & \mapsto & \sharp\sharp\sharp 101 \: r_0' 0\: \sharp\sharp &\\ \mapsto & \sharp\sharp\sharp 1010 \: r_0' \sharp\: \sharp & \mapsto & \sharp\sharp\sharp 101 \: q_0 0\: \sharp\sharp & \mapsto & \sharp\sharp\sharp 10 \: l 1\: \sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp \: 1 l 0\: 1\sharp\sharp\sharp &\\ \mapsto & \sharp\sharp\sharp \: l 1\: 01\sharp\sharp\sharp & \mapsto & \sharp\sharp \: l \sharp \: 101\sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp \: s_0 1\: 01\sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp \: r_1 0\: 1 \sharp\sharp\sharp &\\ \mapsto & \sharp\sharp\sharp\sharp 0 \: r_1 1\: \sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp 01 \: r_1' \sharp\: \sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp 0\: q_1 1\: \sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp \: l 0\: \sharp \sharp\sharp\sharp &\\ \mapsto & \sharp\sharp\sharp \: l \sharp \: 0 \sharp\sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp \: s_0 0 \: \sharp \sharp\sharp\sharp & \mapsto & \sharp\sharp\sharp\sharp \sharp \: r_0 \sharp \: \sharp\sharp\sharp & \mapsto& \sharp\sharp\sharp\sharp \sharp \: s_R \sharp \: \sharp\sharp\sharp& \circlearrowleft\\ \end{array} }

Na ostatniej otrzymanej konfiguracji maszyna się zatrzymuje (następne konfiguracje są identyczne). Zatem konfiguracja początkowa Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \sharp \:s_0 1\: 010101 \sharp} 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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{u\clubsuit w\: : \: u,w\in \left\{0,1\right\}^*\right\} }

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. słowie $w_2=\mathrm{♣}01\mathrm{♣}$
4. oraz 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

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\} }

Ćwiczenie 7

Uzasadnij, że 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\} }

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