Języki, automaty i obliczenia/Ćwiczenia 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 12

Ćwiczenie 1

Rozważmy maszynę Turinga z wykładu (Przykład 1.2) akceptującą język palindromów, czyli:

Sprawdź, że:

oraz że

  1. .
Wskazówka
Rozwiązanie

Ćwiczenie 2

Niech będzie dany alfabet . Zaprojektuj maszynę Turinga akceptująca język postaci:

Zaprojektuj maszynę Turinga , która akceptuje język . Następnie:

  1. Wypisz elementy składowe maszyny , tzn. zbiory oraz funkcję przejścia (zapewnij, aby ).
  2. Wykonaj symulację maszyny na słowie ,
  3. na słowie ,
  4. oraz na słowie .
Wskazówka
Rozwiązanie

Ćwiczenie 3

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

wykazując, że NP .

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

Ćwiczenie 4

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Wskazówka
Rozwiązanie

Ćwiczenie 5

Uzasadnij, że funkcja jest konstruowalna pamięciowo.

Wskazówka
Rozwiązanie
Zadania domowe

Ćwiczenie 6

Skonstruuj maszynę Turinga akceptującą język:

Ćwiczenie 7

Uzasadnij, że język

jest rozpoznawany przez pewną niedeterministyczna maszynę Turinga .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego przeprowadź weryfikację w trzech etapach: konstrukcja słów , gdzie (wyrocznia), sklejanie, weryfikacja, czy .