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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 14

Ćwiczenie 1

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

Wskazówka
Rozwiązanie

Ćwiczenie 2

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

Wskazówka
Rozwiązanie

Ć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:

Wskazówka
Rozwiązanie

Ćwiczenie 4

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

Rozwiązanie

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

Wskazówka
Rozwiązanie
ZADANIA DOMOWE


Ć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:

  1. , ,

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