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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Forys (dyskusja | edycje)
60 edycji
Forys (dyskusja | edycje)
60 edycji
Linia 45: Linia 45:
{{cwiczenie|10||
{{cwiczenie|10||
Skonstruuj maszynę Turinga akceptującą słowo <math>\displaystyle u=1^n</math> w dokładnie <math>\displaystyle n^2</math> krokach. Jak zmodyfikować konstrukcję maszyny, aby akceptowała słowo <math>\displaystyle u</math> dokładnie w <math>\displaystyle 2^n</math> krokach?
Skonstruuj maszynę Turinga akceptującą słowo <math>\displaystyle u=1^n</math> w dokładnie <math>\displaystyle n^2</math> krokach. Jak zmodyfikować konstrukcję maszyny, aby akceptowała słowo <math>\displaystyle u</math> dokładnie w <math>\displaystyle 2^n</math> krokach?
}}
{{cwiczenie|11||
Wypisz dokładnie wszystkie elementy składowe maszyn Turinga
rozpoznających języki zadane gramatykami:
# <math>\displaystyle S\rightarrow AbC</math>  ,  <math>\displaystyle A\rightarrow
aAb|1</math>, <math>\displaystyle C\rightarrow bCc|1</math>
# <math>\displaystyle S\rightarrow ABACA\quad , \quad A\rightarrow Aa|a \quad,\quad B\rightarrow bb|b\quad ,\quad C\rightarrow c|1.</math>
}}
{{cwiczenie|12||
Wykaż (podając ideę kontrukcji), że dla maszyn Turinga <math>\displaystyle TM_1</math>, <math>\displaystyle TM_2</math>
istnieje maszyna Turinga <math>\displaystyle \mathcal{M}</math> rozpoznająca język:
<center><math>\displaystyle  L(
\mathcal{M})=\left\{uv\; : \; u\in L(TM_1), v\in L(TM_2)\right\}.
</math></center>
}}
{{cwiczenie|13||
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\\a^2 b\end{array} \right]\; ,\;
(u_2,v_2)=\left [ \begin{array} {c} ba^2\\a^2 \end{array} \right]
</math></center>
# <center><math>\displaystyle
(u_1,v_1)=\left [ \begin{array} {c} a^b\\a \end{array} \right]\; ,\;
(u_2,v_2)=\left [ \begin{array} {c} a\\b a^2 \end{array} \right]
</math></center>
# <center><math>\displaystyle
(u_1,v_1)=\left [ \begin{array} {c} aaa\\a \end{array} \right], (u_2,v_2)=\left [ \begin{array} {c} b\\b a \end{array} \right], (u_3,v_3)=\left [ \begin{array} {c} bb\\b \end{array} \right], (u_4,v_4)=\left [ \begin{array} {c} ba\\ab \end{array} \right]
</math></center>
}}
{{cwiczenie|14||
Udowodnij Twierdzenie&nbsp;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  <math>\displaystyle a  </math> , jest postaci  <math>\displaystyle v\longrightarrow a  </math> .
}}
}}

Wersja z 15:32, 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=w1w1w2w2…wnwn.


ZADANIA DOMOWE


Ćwiczenie 3

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 4

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?

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Języki,_automaty_i_obliczenia/Ćwiczenia_13:_Złożoność_obliczeniowa.&oldid=40363”