Języki, automaty i obliczenia/Ćwiczenia 14: Języki maszyn Turinga i typu (0). Rozstrzygalność

Z Studia Informatyczne
< Języki, automaty i obliczenia
Wersja z dnia 13:34, 3 wrz 2006 autorstwa Adamroman (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 13

Ćwiczenie 1

W trakcie wykładu rozważaliśmy język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{3^k\: : \: k=i\cdot j } dla pewnych

wykazując, że NP .

Uzasadnij, że także
P
Wskazówka
Rozwiązanie

Ćwiczenie 2

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Wskazówka
Rozwiązanie

Ćwiczenie 3

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Wskazówka
Rozwiązanie

Ćwiczenie 4

Skonstruuj maszynę Turinga rozpoznającą język zadany gramatyką:

Wskazówka
Rozwiązanie

Ćwiczenie 5

Przedstaw ideę działania maszyny Turinga rozpoznającej język

Wskazówka
Rozwiązanie

Ćwiczenie 6

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 , istnieje maszyna o własności:

Wskazówka
Rozwiązanie

Ćwiczenie 7

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

Rozwiązanie

Ćwiczenie 8

W definicji problemu Posta zakłada się, że alfabet zawiera co najmniej dwa elementy. Wykaż, że gdy to założenie nie jest spełnione (tzn. ) problem Posta jest problemem rozstrzygalnym.

Wskazówka
Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 9

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

Ćwiczenie 10

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 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 11

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 12

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Ćwiczenie 13

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 14

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

  1. , ,

Ćwiczenie 15

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

Ćwiczenie 16

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

Ćwiczenie 17

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 .