Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.

Ć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ć $L_1\in$ 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 $L_2\in$ NP .

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

ZADANIA DOMOWE

Ćwiczenie 8

Uzasadnij, że jeśli funkcja $s(n)$ jest konstruowalna pamięciowo, to obliczenie $d_1{\mapsto }^{*}{d}_2$ z definicji konstruowalności pamięciowej (tzn. $d_1=\mathrm{♯}{s}_0{1}^n\mathrm{♯}$, $d_2=\mathrm{♯}{s}_1{1}^{s(n)}w\mathrm{♯}$) następuje w co najwyżej $c{2}^{s(n)}$ krokach, gdzie $c$ jest pewną stałą niezależną od $n$.
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 9

Uzasadnij, że funkcja $n^3$ jest konstruowalna pamięciowo.

Ćwiczenie 10

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

Ćwiczenie 11

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

1. $S\to AbC$ , $A\to aAb|1$, $C\to bCc|1$
2. $S\to ABACA,A\to Aa|a,B\to bb|b,C\to c|1.$

Ćwiczenie 12

Wykaż (podając ideę kontrukcji), że dla maszyn Turinga $T{M}_1$, $T{M}_2$ istnieje maszyna Turinga ${ℳ}$ rozpoznająca język:

$L({ℳ})=\{uv:u\in L(T{M}_1),v\in L(T{M}_2)\}.$

Ćwiczenie 13

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

1. $(u_1,v_1)=\left[\begin{array}{c}a\\ a^{2}b\end{array}\right],(u_2,v_2)=\left[\begin{array}{c}b{a}^2\\ a^2\end{array}\right]$
2. $(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]$
3. $(u_1,v_1)=\left[\begin{array}{c}aaa\\ a\end{array}\right],(u_2,v_2)=\left[\begin{array}{c}b\\ ba\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]$

Ć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 $v⟶a$ .