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

From Studia Informatyczne

Ćwiczenia 12

Ćwiczenie 1

Rozważmy maszynę Turinga \displaystyle TM_2 z wykładu (Przykład 1.2) akceptującą język palindromów, czyli:

\displaystyle  L=\left\{w \overleftarrow{w} \: : \: w\in \left\{0,1\right\}^*\right\}.

Sprawdź, że:

  1. \displaystyle 101101\in L(TM_2)

oraz że

  1. \displaystyle 1010101\not\in L(TM_2).

Wskazówka

Aby wykonać (1), rozpocznij od konfiguracji \displaystyle \sharp \: s_0 1 \: 01101 \sharp, a następnie wykonuj przejścia, zgodnie z diagramem przejść maszyny \displaystyle TM_2 z wykładu.

Rozwiązanie

(Ad. 1) Wykonujemy symulację maszyny \displaystyle TM_2 na pierwszym ze słów:

\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 \displaystyle \sharp \:s_0 1\: 01101 \sharp \mapsto^* \sharp\sharp\sharp\sharp \: s_A \sharp\: \sharp\sharp\sharp. Stan \displaystyle s_A\in S_F, zatem wprost z definicji \displaystyle 101101\in L(TM_2).

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

\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 \displaystyle \sharp \:s_0 1\: 010101 \sharp prowadzić może poprzez relację \displaystyle \mapsto^* tylko do konfiguracji (obliczeń wykonanych) wypisanych powyżej. Żadna z otrzymanych konfiguracji pośrednich nie zawiera stanu ze zbioru \displaystyle S_F. To z kolei oznacza, że \displaystyle 1010101\not\in L(TM_2).

Ćwiczenie 2

Niech będzie dany alfabet \displaystyle \Sigma_I =\left\{0,1,\clubsuit\right\}. Zaprojektuj maszynę Turinga akceptująca język postaci:

\displaystyle  L=\left\{u\clubsuit w\: : \: u,w\in \left\{0,1\right\}^*\right\}.

Zaprojektuj maszynę Turinga \displaystyle \mathcal{M}=(\Sigma _{T},S,f,s_{0},S_{F}), która akceptuje język \displaystyle L. Następnie:

  1. Wypisz elementy składowe maszyny \displaystyle \mathcal{M}, tzn. zbiory \displaystyle \Sigma_T,S,S_{F} oraz funkcję przejścia \displaystyle f (zapewnij, aby \displaystyle s_0\in  S).
  2. Wykonaj symulację maszyny \displaystyle \mathcal{M} na słowie \displaystyle w_1=1100\clubsuit 11,
  3. na słowie \displaystyle w_2=\clubsuit 01 \clubsuit,
  4. oraz na słowie \displaystyle 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 \displaystyle \clubsuit, oznacz to w stanach maszyny.
  3. Jeśli napotkasz symbol \displaystyle \clubsuit ponownie, to odrzuć.
  4. Gdy dotarłeś do prawego ogranicznika i nie napotkałeś \displaystyle \clubsuit, to odrzuć; w przeciwnym przypadku akceptuj.

Rozwiązanie

(Ad. 1) Wypiszemy maszynę \displaystyle \mathcal{M}=(\Sigma _{T},S,f,s_{0},S_{F}) działającą według zaproponowanego we wskazówce schematu. Zbiór \displaystyle \Sigma_I oraz stan początkowy \displaystyle s_0 zostały narzucone treścią zadania. Oznaczamy kolejno:

\displaystyle  \Sigma_T=\left\{0,1,\clubsuit,\sharp\right\}\quad,\quad S=\left\{s_0,s_1,s_R,s_A\right\}\quad,\quad S_F=\left\{s_A\right\}

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

\displaystyle (s_0,0)\mapsto (s_0,0,1) \displaystyle (s_0,1)\mapsto (s_0,1,1) \displaystyle (s_0,\clubsuit)\mapsto (s_1,\clubsuit,1) \displaystyle (s_0,\sharp)\mapsto (s_R,\sharp,0)
\displaystyle (s_1,0)\mapsto (s_1,0,1) \displaystyle (s_1,1)\mapsto (s_1,1,1) \displaystyle (s_1,\clubsuit)\mapsto (s_R,\clubsuit,0)

\displaystyle (s_1,\sharp)\mapsto (s_A,\sharp,0)

\displaystyle (s_R,\clubsuit)\mapsto (s_R,\clubsuit,0) \displaystyle (s_R,\sharp)\mapsto (s_R,\sharp,0)
\displaystyle (s_A,\sharp)\mapsto (s_A,\sharp,0)

Wykonujemy kolejno symulację maszyny Turinga \displaystyle \mathcal{M} na słowach:
(Ad. 2) \displaystyle w_1=1100\clubsuit 11

\displaystyle  \begin{array} {c c c c c c c c} &\sharp s_0 1100\clubsuit 11\sharp & \mapsto & \sharp 1 s_0 100\clubsuit 11\sharp &\mapsto & \sharp 11 s_0 00\clubsuit 11\sharp &\mapsto & \sharp 110 s_0 0\clubsuit 11\sharp \\ \mapsto & \sharp 1100 s_0 \clubsuit 11\sharp & \mapsto &  \sharp 1100\clubsuit s_1 11\sharp  &\mapsto & \sharp 1100\clubsuit 1 s_1 1\sharp &\mapsto & \sharp 1100\clubsuit 11  s_1 \sharp \\ \mapsto & \sharp 1100\clubsuit 11  s_A \sharp & \circlearrowleft \end{array}

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


(Ad. 3) \displaystyle w_2=\clubsuit 01 \clubsuit

\displaystyle  \begin{array} {c c c c c c c c} & \sharp s_0 \clubsuit 01 \clubsuit \sharp & \mapsto & \sharp\clubsuit s_1 01 \clubsuit\sharp  &\mapsto & \sharp\clubsuit 0 s_1 1 \clubsuit\sharp &\mapsto & \sharp\clubsuit 01 s_1 \clubsuit\sharp \\ \mapsto & \sharp\clubsuit 01 s_R \clubsuit\sharp & \circlearrowleft \end{array}

Żadna z otrzymanych konfiguracji nie była akceptująca, zatem \displaystyle w_2\not\in L(\mathcal{M}).


(Ad. 4) \displaystyle w_3=0000110

\displaystyle  \begin{array} {c c c c c c c c} & \sharp s_0 0000110 \sharp & \mapsto & \sharp 0 s_0 000110 \sharp &\mapsto & \sharp 00 s_0 00110 \sharp &\mapsto & \sharp 000 s_0 0110 \sharp \\ \mapsto & \sharp 0000 s_0 110 \sharp & \mapsto & \sharp 00001 s_0 10 \sharp  &\mapsto & \sharp 000011  s_0 0 \sharp  &\mapsto & \sharp 0000110 s_0 \sharp \\ \mapsto & \sharp 0000110 s_R \sharp & \circlearrowleft \end{array}

Tak jak w poprzednim przypadku \displaystyle w_3\not\in L(\mathcal{M}).

Ćwiczenie 3

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

\displaystyle  L=\left\{3^k\: : \: k=i\cdot j dla pewnych \displaystyle   i,j> 1\right\},

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

Uzasadnij, że także
\displaystyle L\in P \displaystyle  .

Wskazówka

Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie \displaystyle i,j>1, dla których \displaystyle k=i\cdot j.

Rozwiązanie

Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie \displaystyle k^2 (wielomianową ilość) mnożeń. Sama weryfikacja zależności \displaystyle 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 \displaystyle 1 jest tylko do odczytu. Mamy na niej słowo \displaystyle 3^k.
  2. Rozpocznij od zapisania słowa \displaystyle 11 na taśmie nr \displaystyle 2 i słowa \displaystyle 22 na taśmie nr \displaystyle 3.
  3. Przepisz słowa na taśmę nr \displaystyle 4 według kolejności taśm \displaystyle 2,3,1.
  4. Sprawdź na taśmie nr \displaystyle 4 czy \displaystyle k=i\cdot j. Jeśli tak, to akceptuj. Inaczej krok następny.
  5. Dopisz symbol \displaystyle 1 na taśmie nr \displaystyle 2. Gdy powstało słowo dłuższe niż \displaystyle k, dopisz symbol \displaystyle 2 na taśmie nr \displaystyle 3, a słowo na taśmie nr \displaystyle 2 usuń i zapisz na niej słowo \displaystyle 11.
  6. Jeśli słowo na taśmie nr \displaystyle 3 jest dłuższe niż \displaystyle k, to odrzuć. W przeciwnym przypadku przejdź do kroku 3.

Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr \displaystyle 2 (licznik 1) i \displaystyle 3 (licznik 2) jako liczniki, a na taśmie \displaystyle 4 wykonuj symulacje. Zacznij od stanu liczników na \displaystyle 2 i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej \displaystyle 2) i zwiększ licznik \displaystyle 2. Gdy on także się przepełni, to iloczyn stanów liczników przekracza \displaystyle 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 \displaystyle n).

Dla małych \displaystyle n możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. Zatem \displaystyle L\in P .

Ćwiczenie 4

Uzasadnij, że funkcja \displaystyle s(n)=3n jest konstruowalna pamięciowo.

Wskazówka

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

Rozwiązanie

Bierzemy maszynę \displaystyle MT_4 z wykładu konstruującą funkcję \displaystyle 2n. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez \displaystyle I oraz \displaystyle 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ę \displaystyle \mathcal{M} według schematu:

  1. Jeśli słowo wejściowe jest puste, to stop.
  2. Jeśli słowo wejściowe jest inne niż \displaystyle 1^n, to odrzuć.
  3. Przepisz słowo wejściowe tak, aby znajdowało się na taśmie \displaystyle I, a taśma \displaystyle 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ę \displaystyle S.
  5. Symulujemy maszynę \displaystyle MT_4 na taśmie \displaystyle S.
  6. Dopisujemy do taśmy \displaystyle S słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie \displaystyle 3n komórek taśmy.
  7. Zamieniamy symbole na \displaystyle 1 (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy do konfiguracji końcowej \displaystyle s_1\in S_F.

Po zakończeniu cyklu doszliśmy do konfiguracji \displaystyle \sharp s_1 1^{3n} \sharp, co było wymagane w definicji.

Ćwiczenie 5

Uzasadnij, że funkcja \displaystyle s(n)=3^n jest konstruowalna pamięciowo.

Wskazówka

Wykorzystaj konstruowalność pamięciową funkcji \displaystyle g(n)=3n.

Rozwiązanie

Wykorzystujemy trzy taśmy (\displaystyle I, \displaystyle C, \displaystyle S) oraz maszynę \displaystyle \mathcal{M} konstruującą pamięciowo funkcję \displaystyle g(n)=3n. Docelowa maszyna \displaystyle \mathcal{N} działa według schematu.

  1. Jeśli słowo początkowe jest puste, wypisz \displaystyle 1 i zatrzymaj się. W przeciwnym wypadku, wykonaj następny krok.
  2. Jeśli słowo wejściowe jest inne niż \displaystyle 1^n, to odrzuć.
  3. Na taśmie \displaystyle I wypisz słowo wejściowe, na taśmach \displaystyle C i \displaystyle S wypisz słowo \displaystyle 1.
  4. Wykonaj symulację maszyny \displaystyle \mathcal{M} na taśmie \displaystyle S oraz dopisz symbol \displaystyle 1 do taśmy \displaystyle C (po jednym przebiegu ilość symboli na taśmie \displaystyle S wzrasta trzykrotnie)
  5. Jeśli słowo na taśmie \displaystyle C jest krótsze niż słowo na taśmie \displaystyle I, wykonaj ponownie krok 4.
  6. W tym momencie na taśmie \displaystyle S zostało zaznaczone \displaystyle 3^n komórek.

Zamieniamy wypisane symbole na \displaystyle 1 (zapominamy o symulacji taśm), wracamy nad pierwszy symbol (przed lewym markerem) i przechodzimy do konfiguracji końcowej \displaystyle s_1\in S_F.

Po zakończeniu cyklu doszliśmy do konfiguracji \displaystyle \sharp s_1 1^{3^n} \sharp, co było wymagane w definicji konstruowalności

pamięciowej.

Zadania domowe

Ćwiczenie 6

Skonstruuj maszynę Turinga \displaystyle \mathcal{MT} akceptującą język:

\displaystyle  L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}.

Ćwiczenie 7

Uzasadnij, że język

\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 \displaystyle \mathcal{NMT}.

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego \displaystyle w przeprowadź weryfikację w trzech etapach: konstrukcja słów \displaystyle w_1, \dots ,w_n, gdzie \displaystyle n< |w| (wyrocznia), sklejanie, weryfikacja, czy \displaystyle w=w_1w_1 w_2 w_2 \dots w_n w_n.