Języki, automaty i obliczenia/Ćwiczenia 14: Języki maszyn Turinga i typu (0). Rozstrzygalność: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\:" na "\ :")
 
Linia 155: Linia 155:
 
przy czym <math>\displaystyle k<l</math> i <math>\displaystyle p>q</math>. W tej sytuacji zachodzi własność Posta. Uzasadnienie jest następujące. Biorąc ciąg:
 
przy czym <math>\displaystyle k<l</math> i <math>\displaystyle p>q</math>. W tej sytuacji zachodzi własność Posta. Uzasadnienie jest następujące. Biorąc ciąg:
  
<center><math>\displaystyle \begin{array} {c c c} (\underbrace{i\;,\; \dots\;,\;i}&,&\underbrace{j\;,\;\dots\;,\;j})\\ {\displaystyle p-q \mbox{ razy}\displaystyle && {\displaystyle l-k \mbox{ razy}\displaystyle \end{array}</math></center>
+
<center><math>  
 +
\begin{array} {c c c}
 +
(\underbrace{i\;,\; \dots\;,\;i}_{p-q \text{ razy}} & , & \underbrace{j\;,\;\dots\;,\;j}_{l-k \text{ razy}})\\
 +
\end{array}</math></center>
  
 
otrzymujemy słowa:
 
otrzymujemy słowa:

Aktualna wersja na dzień 21:45, 24 wrz 2020

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