Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Forys (dyskusja | edycje)
Forys (dyskusja | edycje)
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||

Wersja z 15:22, 3 wrz 2006

Ćwiczenia 13

Ćwiczenie 1

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ć L1 P .

Ćwiczenie 2

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 L2 NP .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego w przeprowadź weryfikację w trzech etapach: konstrukcja słów w1,,wn, gdzie n<|w| (wyrocznia), sklejanie, weryfikacja, czy w=w1w1w2w2wnwn.


ZADANIA DOMOWE


Ćwiczenie 8

Uzasadnij, że jeśli funkcja s(n) jest konstruowalna pamięciowo, to obliczenie d1*d2 z definicji konstruowalności pamięciowej (tzn. d1=s01n, d2=s11s(n)w) następuje w co najwyżej c2s(n) krokach, gdzie c jest pewną stałą niezależną od n.
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 9

Uzasadnij, że funkcja n3 jest konstruowalna pamięciowo.

Ćwiczenie 10

Skonstruuj maszynę Turinga akceptującą słowo u=1n w dokładnie n2 krokach. Jak zmodyfikować konstrukcję maszyny, aby akceptowała słowo u dokładnie w 2n krokach?

Ćwiczenie 11

Wypisz dokładnie wszystkie elementy składowe maszyn Turinga rozpoznających języki zadane gramatykami:

  1. SAbC , AaAb|1, CbCc|1
  2. SABACA,AAa|a,Bbb|b,Cc|1.

Ćwiczenie 12

Wykaż (podając ideę kontrukcji), że dla maszyn Turinga TM1, TM2 istnieje maszyna Turinga rozpoznająca język:

L()={uv:uL(TM1),vL(TM2)}.

Ćwiczenie 13

Czy któraś z poniższych list słów ma własność Posta?

  1. (u1,v1)=[aa2b],(u2,v2)=[ba2a2]
  2. (u1,v1)=[aba],(u2,v2)=[aba2]
  3. (u1,v1)=[aaaa],(u2,v2)=[bba],(u3,v3)=[bbb],(u4,v4)=[baab]

Ć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 va .