|
|
Linia 3: |
Linia 3: |
|
| |
|
| {{cwiczenie|1|| | | {{cwiczenie|1|| |
| Skonstruuj maszynę Turinga rozpoznającą język zadany gramatyką:
| |
| <center><math>\displaystyle
| |
| S\rightarrow aTb|b \quad, \quad T\rightarrow Ta|1.
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Zacznij od wypisania języka opisanego przez daną gramatykę.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Analizując postać gramatyki, dochodzimy do wniosku, że zadana
| |
| maszyna ma rozpoznawać język postaci:
| |
| <center><math>\displaystyle
| |
| L=\left\{a^n b\: :\; n\geqslant 0\right\}.
| |
| </math></center>
| |
|
| |
| 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 <math>\displaystyle a</math>, wypisz <math>\displaystyle a</math> i przejdź w prawo, powtarzając ten krok. Jeśli czytasz <math>\displaystyle b</math>, przejdź w prawo i wykonaj krok następny.
| |
| # Jeśli jesteś na ograniczniku, to akceptuj, inaczej odrzuć.
| |
|
| |
| </div></div>
| |
|
| |
| {{cwiczenie|2||
| |
| Przedstaw ideę działania maszyny Turinga rozpoznającej język
| |
| <center><math>\displaystyle
| |
| L=\left\{a^n b^{2n} c^{3n} \;:\; n>1\right\}.
| |
| </math></center>
| |
|
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Wykorzystaj kilka taśm oraz konstruowalność pamięciową.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Idea działania poszukiwanej maszyny (czterotaśmowej) jest następująca:
| |
|
| |
| # Sprawdź czy słowo wjeściowe <math>\displaystyle w</math> zawiera jako pierwszy symbol <math>\displaystyle a</math>. Jeśli nie, odrzuć.
| |
| # Skopiuj najdłuższy prefiks słowa wejściowego <math>\displaystyle w</math> postaci <math>\displaystyle a^k</math> na taśmę nr 2.
| |
| # Korzystając z konstruowalności pamięciowej funkcji <math>\displaystyle 2k</math> oraz <math>\displaystyle 3k</math> wypisz słowo <math>\displaystyle b^{2k}</math> na taśmie nr <math>\displaystyle 3</math> oraz słowo <math>\displaystyle c^{3k}</math> na taśmie nr <math>\displaystyle 4</math>.
| |
| # Dopisz słowo z taśmy nr <math>\displaystyle 3</math> i <math>\displaystyle 4</math> do słowa na taśmie nr <math>\displaystyle 2</math>. W tym momencie na taśmie nr <math>\displaystyle 2</math> znajduje się słowo <math>\displaystyle a^k b^{2k} c^{3k}</math>.
| |
| # Porównaj słowo z taśmy nr <math>\displaystyle 2</math> ze słowem <math>\displaystyle w</math>. Jeśli są identyczne, to akceptuj.
| |
|
| |
| </div></div>
| |
|
| |
| {{cwiczenie|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 <math>\displaystyle TM_1</math>, <math>\displaystyle TM_2</math> istnieje maszyna <math>\displaystyle \mathcal{M}</math> o własności:
| |
|
| |
| # <math>\displaystyle L( \mathcal{M})=L(TM_1)\cup L(TM_2), </math>
| |
| # <math>\displaystyle L( \mathcal{M})=L(TM_1)\cap L(TM_2). </math>
| |
|
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Wykonaj odpowiednią symulację maszyn <math>\displaystyle TM_1</math> oraz <math>\displaystyle TM_2</math>.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| '''(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 <math>\displaystyle TM_1</math> na taśmie <math>\displaystyle 1</math> i jeden krok <math>\displaystyle TM_2</math> na taśmie <math>\displaystyle 2</math>.
| |
| # 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).
| |
| </div></div>
| |
|
| |
| {{cwiczenie|4||
| |
| Czy któraś z poniższych list słów ma własność Posta?
| |
| # <center><math>\displaystyle
| |
| (u_1,v_1)=\left [ \begin{array} {c} a^2 \\ a^2 b\end{array} \right]\;
| |
| ,\; (u_2,v_2)=\left [
| |
| \begin{array} {c} b^2 \\ ba
| |
| \end{array} \right]\; ,\; (u_3,v_3)=\left [ \begin{array} {c} ab^2 \\ b\end{array} \right]
| |
| </math></center>
| |
| # <center><math>\displaystyle
| |
| (u_1,v_1)=\left [ \begin{array} {c} a \\ b^2\end{array} \right]\; ,\;
| |
| (u_2,v_2)=\left [
| |
| \begin{array} {c}
| |
| a^2
| |
| \\b
| |
| \end{array} \right]
| |
| </math></center>
| |
| # <center><math>\displaystyle (u_1,v_1)=\left [ \begin{array} {c} ba \\ abab\end{array} \right], (u_2,v_2)=\left [\begin{array} {c}b\\a\end{array} \right], (u_3,v_3)=\left [\begin{array} {c}aba\\b\end{array} \right], (u_4,v_4)=\left [\begin{array} {c}aa\\a\end{array} \right]</math></center>
| |
|
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| '''(Ad. 1)''' Rozważmy ciąg indeksów <math>\displaystyle (1,2,1,3)</math>. Otrzymujemy:
| |
| <center><math>\displaystyle
| |
| \left [ \begin{array} {c} a^2 \\ a^2 b\end{array} \right] \left
| |
| [\begin{array} {c} b^2 \\ ba\end{array} \right] \left [
| |
| \begin{array} {c} a^2 \\ a^2 b\end{array} \right] \left [
| |
| \begin{array} {c} ab^2 \\ b\end{array} \right]
| |
| =\left [ \begin{array} {c} a^2 b^2 a^2 ab^2\\ a^2 b ba a^2 b b
| |
| \end{array} \right]=\left [ \begin{array} {c} a^2 b^2 a^3 b^2\\ a^2 b^2 a^3 b^2
| |
| \end{array} \right]
| |
| </math></center>
| |
|
| |
| 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 <math>\displaystyle a^k</math>, a drugie <math>\displaystyle b^j</math>, dla pewnych <math>\displaystyle k,j>0</math>. Ale zawsze <math>\displaystyle a^k \neq b^j</math>, czyli własność Posta nie może zachodzić.
| |
|
| |
| '''(Ad. 3)''' Rozważmy ciąg indeksów <math>\displaystyle (4,2,3,2,3,1,1)</math>.
| |
| Zestawiając zadane pary słów w tej kolejności, otrzymujemy:
| |
| <center><math>\displaystyle
| |
| \left [\begin{array} {c} aa\\a\end{array} \right] \left [
| |
| \begin{array} {c} ba \\ abab\end{array} \right]
| |
| \left [ \begin{array} {c} ba \\ abab\end{array} \right] \left [
| |
| \begin{array} {c} b\\a \end{array} \right] \left [
| |
| \begin{array} {c} aba \\b \end{array} \right] \left [
| |
| \begin{array} {c} b\\a \end{array} \right]
| |
| \left [\begin{array} {c} aa\\a\end{array} \right]
| |
| </math></center>
| |
|
| |
| <center><math>\displaystyle
| |
| = \left [\begin{array} {c}
| |
| aabababababaa\\aabababababaa\end{array} \right]
| |
| </math></center>
| |
|
| |
| W ten sposób wykazaliśmy, że własność Posta zachodzi.
| |
| </div></div>
| |
|
| |
| {{cwiczenie|5||
| |
| W definicji problemu Posta zakłada się, że alfabet <math>\displaystyle \mathcal{A}</math>
| |
| zawiera co najmniej dwa elementy. Wykaż, że gdy to założenie nie jest spełnione (tzn. <math>\displaystyle \mathcal{A}=\left\{1\right\}</math>) problem Posta jest problemem rozstrzygalnym.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
| |
| Rozważ dwa przypadki, zależnie od tego, czy lista zawiera tylko pary słów postaci <math>\displaystyle (a^k,a^j)</math>, gdzie <math>\displaystyle k>j</math> (lub tylko <math>\displaystyle k<j</math>), czy też jeszcze jakieś inne pary słów.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Rozważmy listę par słów <math>\displaystyle (u_1,v_1),\dots, (u_n,v_n)</math> nad alfabetem
| |
| <math>\displaystyle \mathcal{A}</math>. Przedstawimy algorytm sprawdzający, czy lista ma
| |
| własność Posta:
| |
|
| |
| # Jeśli lista zawiera parę <math>\displaystyle (1^k,1^k)</math>, to mamy własność Posta.
| |
| # Jeśli jedyne pary to takie, w których <math>\displaystyle (u_i,v_i)=(1^{k_i},1^{l_i})</math> oraz <math>\displaystyle k_i>l_i</math> (lub <math>\displaystyle k_i<l_i</math>), dla
| |
| <math>\displaystyle i=1,\dots,n</math>, to własność Posta nie jest spełniona (słowo dane przez
| |
| katenację dowolnych <math>\displaystyle u_i</math> zawsze zawiera więcej (odp. mniej) symboli
| |
| niż odpowiadająca mu katenacja słow <math>\displaystyle v_i</math> )
| |
| # W ostatnim przypadku istnieją indeksy <math>\displaystyle i,j</math> takie, że
| |
| <center><math>\displaystyle (u_i,v_i)=(1^k,1^l)\quad , \quad (u_j,v_j)=(1^p,1^q), </math></center>
| |
|
| |
| przy czym <math>\displaystyle k<l</math> i <math>\displaystyle p>q</math>. W tej sytuacji zachodzi własność Posta. Uzasadnienie jest następujące. Biorąc ciąg:
| |
|
| |
| <center><math>\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}</math></center>
| |
|
| |
| otrzymujemy słowa:
| |
| <center><math>\displaystyle
| |
| \left [ \begin{array} {c} u_1\\ v_1 \end{array} \right ]^{p-q} \left [
| |
| \begin{array} {c} u_2\\ v_2 \end{array} \right ]^{l-k}=
| |
| \left [ \begin{array} {c} 1^k\\ 1^l \end{array} \right ]^{p-q}\left [
| |
| \begin{array} {c} 1^p\\ 1^1 \end{array} \right ]^{l-k}=
| |
| \left [ \begin{array} {c} 1^{k(p-q)}\\1^{l(p-q)}\end{array} \right ]
| |
| \left [
| |
| \begin{array} {c}1^{p (l-k)}\\
| |
| 1^{q(l-k)} \end{array} \right ]
| |
| </math></center>
| |
|
| |
| <center><math>\displaystyle
| |
| =\left [ \begin{array} {c} 1^{kp-kq+pl-pk}\\1^{lp-lq+ql-qk}
| |
| \end{array} \right ]=\left [ \begin{array} {c} 1^{lp-kq}\\1^{lp-kq}
| |
| \end{array} \right ]
| |
| </math></center>
| |
|
| |
| 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.
| |
| </div></div>
| |
|
| |
| <center>ZADANIA DOMOWE</center>
| |
|
| |
| {{cwiczenie|6||
| |
| Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga | | Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga |
| <math>\displaystyle \mathcal{MT}</math> akceptującej język: | | <math>\displaystyle \mathcal{MT}</math> akceptującej język: |
Linia 189: |
Linia 12: |
| }} | | }} |
|
| |
|
| {{cwiczenie|7|| | | {{cwiczenie|2|| |
| Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga | | Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga |
| <math>\displaystyle \mathcal{NMT}</math> akceptującej język: | | <math>\displaystyle \mathcal{NMT}</math> akceptującej język: |
Linia 203: |
Linia 26: |
| etapach: konstrukcja słów <math>\displaystyle w_1, \dots ,w_n</math>, gdzie <math>\displaystyle n< |w|</math> (wyrocznia), sklejanie, weryfikacja, czy <math>\displaystyle w=w_1w_1 w_2 w_2 \dots w_n w_n</math>. | | etapach: konstrukcja słów <math>\displaystyle w_1, \dots ,w_n</math>, gdzie <math>\displaystyle n< |w|</math> (wyrocznia), sklejanie, weryfikacja, czy <math>\displaystyle w=w_1w_1 w_2 w_2 \dots w_n w_n</math>. |
| }} | | }} |
| | |
| | |
| | <center>ZADANIA DOMOWE</center> |
| | |
|
| |
|
| {{cwiczenie|8|| | | {{cwiczenie|8|| |