Języki, automaty i obliczenia/Ćwiczenia 14: Języki maszyn Turinga i typu (0). Rozstrzygalność
Ćwiczenia 14
Ćwiczenie 1
Skonstruuj maszynę Turinga rozpoznającą język zadany gramatyką:
Ćwiczenie 2
Przedstaw ideę działania maszyny Turinga rozpoznającej język
Ćwiczenie 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
, istnieje maszyna o własności:Ćwiczenie 4
Czy któraś z poniższych list słów ma własność Posta?
Ćwiczenie 5
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.
Ćwiczenie 6
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 7
Wypisz dokładnie wszystkie elementy składowe maszyn Turinga rozpoznających języki zadane gramatykami:
- , ,
Ćwiczenie 8
Wykaż (podając ideę kontrukcji), że dla maszyn Turinga
, istnieje maszyna Turinga rozpoznająca język:Ćwiczenie 9
Czy któraś z poniższych list słów ma własność Posta?
Ćwiczenie 10
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 .