Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami
Linia 31: | Linia 31: | ||
{{cwiczenie| | {{cwiczenie|3|| | ||
Uzasadnij, że jeśli funkcja <math>\displaystyle s(n)</math> jest konstruowalna pamięciowo, to obliczenie <math>\displaystyle d_1 \mapsto^* d_2</math> z definicji | Uzasadnij, że jeśli funkcja <math>\displaystyle s(n)</math> jest konstruowalna pamięciowo, to obliczenie <math>\displaystyle d_1 \mapsto^* d_2</math> z definicji | ||
konstruowalności pamięciowej (tzn. <math>\displaystyle d_1=\sharp s_0 1^n \sharp</math>, | konstruowalności pamięciowej (tzn. <math>\displaystyle d_1=\sharp s_0 1^n \sharp</math>, | ||
Linia 39: | Linia 39: | ||
}} | }} | ||
{{cwiczenie| | {{cwiczenie|4|| | ||
Uzasadnij, że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo. | Uzasadnij, że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo. | ||
}} | }} |
Wersja z 15:23, 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:
Zmodyfikuj, ewentualnie, tę konstrukcję , aby udowodnić P .
Ćwiczenie 2
Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga akceptującej język:
Zmodyfikuj, ewentualnie, tę konstrukcję aby udowodnić, że
NP .
Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego przeprowadź weryfikację w trzech etapach: konstrukcja słów , gdzie (wyrocznia), sklejanie, weryfikacja, czy .
Ćwiczenie 3
Uzasadnij, że jeśli funkcja jest konstruowalna pamięciowo, to obliczenie z definicji
konstruowalności pamięciowej (tzn. ,
) następuje w co najwyżej krokach, gdzie jest pewną
stałą niezależną od .
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.
Ćwiczenie 4
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 10
Skonstruuj maszynę Turinga akceptującą słowo w dokładnie krokach. Jak zmodyfikować konstrukcję maszyny, aby akceptowała słowo dokładnie w krokach?
Ćwiczenie 11
Wypisz dokładnie wszystkie elementy składowe maszyn Turinga rozpoznających języki zadane gramatykami:
- , ,
Ćwiczenie 12
Wykaż (podając ideę kontrukcji), że dla maszyn Turinga , istnieje maszyna Turinga rozpoznająca język:
Ćwiczenie 13
Czy któraś z poniższych list słów ma własność Posta?
Ć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 , jest postaci .