Języki, automaty i obliczenia/Ćwiczenia 11: Automat ze stosem

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia 11

Ćwiczenie 1

Określ automaty ze stosem akceptujące następujące języki. Ustal, czy akceptacja jest przez pusty stos, czy przez stany końcowe. Czy języki są deterministyczne?

Wszystkie rozważane automaty będą określone grafem, niemniej dla większej czytelności podamy również alfabet stosu.

Rozwiązanie punktu 1
Rozwiązanie punktu 2
Rozwiązanie punktu 3
Rozwiązanie punktu 4

Ćwiczenie 2

Napisz na podstawie dowodu twierdzenia 2.2

  1. algorytm konstrukcji automatu ze stosem rozpoznającego język generowany przez daną gramatykę bezkontekstową w postaci normalnej Greibach,
  2. algorytm konstrukcji gramatyki bezkontekstowej generującej język rozpoznawany przez pusty stos przez dany automat ze stosem.

Ćwiczenie 3

Wykorzystując algorytmy z poprzedniego zadania, określ:

  1. automat akceptujący język generowany przez gramatykę o zbiorze praw
    ,
  2. gramatykę generującą język akceptowany przez pusty stos przez automat zadany rysunkiem:
Rysunek 5

gdzie , a jest symbolem początkowym stosu.


Rozwiązanie

Ćwiczenie 4

Udowodnij, że każdy automat ze stosem, w którym wielkość stosu jest ograniczona pewną stałą, jest równoważny pewnemu automatowi skończenie stanowemu.

Rozwiązanie

Ćwiczenie 5

Oto nieformalny opis automatu z kolejką:

Automat z kolejką jest podobny do automatu ze stosem, ale zamiast stosu (LIFO - last in, first out) posiada kolejkę FIFO (first in, first out). W każdym kroku automat czyta symbol z taśmy (może to być słowo puste), usuwa z kolejki początkowy symbol (być może słowo puste) oraz wstawia na koniec kolejki słowo (być może słowo puste). Automat z kolejką akceptuje słowo przy stanie końcowym lub przy pustej kolejce.

  1. Podaj formalną definicję automatu z kolejką.
  2. Zdefiniuj dwa sposoby akceptacji słowa przez automat: przez stan końcowy oraz przez pustą kolejkę.
Rozwiązanie punktu 1
Rozwiązanie punktu 2

Ćwiczenie 6

Czy moc obliczeniowa automatu z kolejką jest taka sama jak moc automatu ze stosem?

Wskazówka
Rozwiązanie
ZADANIA DOMOWE

Ćwiczenie 7

Określ automaty ze stosem akceptujące następujące języki przez pusty stos i przez stany końcowe. Wskaż, które języki są deterministyczne:

Ćwiczenie 8

Określ automat ze stosem, który rozpoznaje język Łukasiewicza zapisany w wersji postfiksowej (patrz wykład 11, uwagi o języku Łukasiewicza po dowodzie twierdzenia 2.1)