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

From Studia Informatyczne

Ć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 \displaystyle L_i są deterministyczne?

  1. \displaystyle L_1=\{a^{n}b^{n+m}a^{m}:\: m,n\geqslant 1\},
  2. \displaystyle L_2=\left\{ w\overleftarrow{w} : w \in \{ a,b\}^*  \right\},
  3. \displaystyle L_3=\{a^{n}b^m:\:  1\leqslant n\leqslant m\},
  4. \displaystyle L_4=\{w \in \{ a,b\}^+ :\#_a w = \#_b w \}.

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

Rozwiązanie punktu 1

Szukany automat określony jest rysunkiem:

<flash>file=ja-lekcja11-c-rys1.swf|width=250|height=250</flash>

Rysunek 1

gdzie \displaystyle A_S = \{z_0,a,b\}, a \displaystyle z_0 jest symbolem początkowym stosu.

Zauważ, że automat ten akceptuje język \displaystyle L_1 zarówno przez stany końcowe jak i przez pusty stos. Automat jest deterministyczny, a to oznacza, że język \displaystyle L_1 jest też deterministyczny.

Rozwiązanie punktu 2

Szukany automat określony jest rysunkiem:

<flash>file=ja-lekcja11-c-rys2.swf|width=250|height=250</flash>

Rysunek 2

gdzie \displaystyle A_S = \{z_0,a,b\}, a \displaystyle z_0 jest symbolem początkowym stosu i akceptuje język \displaystyle L_2 przez pusty stos.

Automat jest niedeterministyczny i język \displaystyle L_2 też jest niedeterministyczny. Nie wiadomo od której litery czytanego słowa automat powinien wymazywać stos. Dlatego równolegle z wpisywaniem na stos automat zaczyna wymazywać za każdym razem, gdy wystąpią dwie takie same litery obok siebie. Porównaj otrzymany automat z automatami otrzymanymi dla języków \displaystyle L_5 i \displaystyle L_6 z ćwiczenia 1.

Rozwiązanie punktu 3

Szukany automat określony jest rysunkiem:

<flash>file=ja-lekcja11-c-rys3.swf|width=250|height=150</flash>

Rysunek 3

gdzie \displaystyle A_S = \{z_0,a\}, a \displaystyle z_0 jest symbolem początkowym stosu. Automat ten akceptuje język \displaystyle L_3

przez stany końcowe i jest automatem deterministycznym.

Rozwiązanie punktu 4

Szukany automat określony jest rysunkiem:

<flash>file=ja-lekcja11-c-rys4.swf|width=250|height=250</flash>

Rysunek 4

gdzie \displaystyle A_S = \{z_0,a,b \}, a \displaystyle z_0 jest symbolem początkowym stosu. Automat akceptuje język \displaystyle L_4

przez stany końcowe i jest automatem niedeterministycznym. Uzasadnij ten fakt. Czy język \displaystyle L_4 jest językiem niedeterministycznym?

Ć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ę \displaystyle G o zbiorze praw
    \displaystyle  P : v_0 \rightarrow av_0 v_1 \;| \; av_1, v_1 \rightarrow b,
  2. gramatykę generującą język akceptowany przez pusty stos przez automat zadany rysunkiem:



Rysunek 5

gdzie \displaystyle A_S = \{z_0,a\}, a \displaystyle z_0 jest symbolem początkowym stosu.


Rozwiązanie

Zarówno w punkcie 1 jak i 2 rozważanym językiem jest \displaystyle L=\{a^{n}b^n:\:  1\leqslant n\} .
Punkt 1.
Gramatyka jest w postaci Greibach i możemy od razu określić automat. Zgodnie z konstrukcją jest to automat jednostanowy zadany rysunkiem:

<flash>file=ja-lekcja11-c-rys6.swf|width=250|height=250</flash>

Rysunek 6

gdzie \displaystyle A_S = \{v_0,v_1,a,b\}, a \displaystyle v_0 jest symbolem początkowym stosu.

Dla przykładu prześledźmy akceptację przez ten automat słowa \displaystyle a^2b^2.
\displaystyle (v_0,q) |\!\!\!\Longrightarrow (v_1v_0a,q) |\!\!\!\Longrightarrow^a  (v_1v_0,q) |\!\!\!\Longrightarrow (v_1v_1a,q) |\!\!\!\Longrightarrow^a (v_1v_1,q) |\!\!\!\Longrightarrow (v_1b,q) |\!\!\!\Longrightarrow^b (v_1,q)  |\!\!\!\Longrightarrow^b (b,q)|\!\!\!\Longrightarrow^b (1,q)

Punkt 2.

Gramatykę zdefiniujemy przez podanie zbioru praw, wskazując równocześnie, z jakiego przejścia w automacie dane prawo powstało:
\displaystyle v_0\rightarrow (q_0,z_0,q_1)
\displaystyle (q_0,z_0,q_1) \rightarrow a (q_0,a,q_1) \longleftrightarrow (z_0,q_0,a)|\!\!\!\Longrightarrow(a,q_0)
\displaystyle (q_0,a,q_1)\rightarrow a (q_0,a,q_1)(q_1,a,q_1) \longleftrightarrow (a,q_0,a) |\!\!\!\Longrightarrow  (a^2,q_0)
\displaystyle (q_0,a,q_1)\rightarrow b\longleftrightarrow  (a,q_0,b)  |\!\!\!\Longrightarrow (1,q_1)
\displaystyle (q_1,a,q_1) \rightarrow b \longleftrightarrow   (a,q_1,b) |\!\!\!\Longrightarrow (1,q_1).

Zauważmy, że w obu konstrukcjach otrzymujemy gramatykę i automat różne od wyjściowych.

Ć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

Dla dowodu tej równoważności wystarczy, dla automatu ze stosem z ograniczoną wielkością stosu, określić równoważny automat skończenie stanowy. Niech \displaystyle k\geqslant 1 będzie dowolną stałą, a \displaystyle \mathcal{A}_S=(S,A,A_S,f_S,s_0,z_0,S_F) automatem, w którym wielkość stosu ograniczona jest przez stałą \displaystyle k. Równoważny automat skończenie stanowy jest automatem niedeterministycznym z pustymi przejściami.
Niech \displaystyle \mathcal{A}=(S\times T,A,f,(s_0,z_0),F), gdzie \displaystyle T=\{w \in A_s^*: |w|\leqslant k\}, \displaystyle F=S_F\times T,
\displaystyle \forall s,s' \in S, \forall z \in A_S, \forall u,v \in A^*_S, \forall a \in A \cup \{1\}

\displaystyle f((s,uz),a)=\{(s',uv): (uz,s) |\!\!\!\Longrightarrow^a (uv,s')\}.

Co zmieni się w definiowanym automacie skończenie stanowym, jeśli automat ze stosem będzie akceptował przez pusty stos?

Ć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

Automatem z kolejką nad alfabetem \displaystyle A nazywamy system \displaystyle \mathcal{AK}=(Q,A,A_{K},f,s_{0},z_{0},Q_{F}) , w którym
\displaystyle A - jest alfabetem, \displaystyle A_{K} - jest dowolnym skończonym i niepustym zbiorem zwanym alfabetem kolejki (niekoniecznie rozłącznym z \displaystyle A ), \displaystyle Q - jest dowolnym, skończonym i niepustym zbiorem zwanym zbiorem stanów, \displaystyle f:A_{K}\times Q\times (A\cup \left\{ 1\right\} )\longrightarrow  \mathcal{P}_{sk}(A_{K}^{*}\times Q) jest funkcją przejść, której wartościami są skończone podzbiory \displaystyle A_{K}^{*}\times Q (także zbiór pusty), \displaystyle q_{0}\in Q jest stanem początkowym, \displaystyle z_{0}\in  A_{K} symbolem początkowym kolejki, \displaystyle Q_{F}\subset Q zbiorem stanów końcowych.

Rozwiązanie punktu 2

Automat z kolejką \displaystyle \mathcal{AK}=(Q,A,A_{K},f,s_{0},z_{0},Q_{F}) akceptuje przez stan końcowy słowo \displaystyle w=w_1w_2...w_m \in A^* (\displaystyle w_1,  w_2, ..., w_m \in A, m \geqslant 0), jeśli istnieje sekwencja stanów \displaystyle r_0, r_1, ..., r_m oraz słów \displaystyle s_0, s_1, ..., s_m \in A_{K}^* takich, że:

  • \displaystyle r_0 = q_0,
  • \displaystyle s_0 = z_0,
  • \displaystyle (r_{i+1},b) \in f(r_i, w_{i+1}, a), gdzie \displaystyle s_i=au oraz \displaystyle s_{i+1} = ub dla pewnego \displaystyle u \in A_{K}^*,
  • \displaystyle r_m \in Q_{F}.

Automat akceptuje słowo \displaystyle w przez pustą kolejkę przy takich samych warunkach jak powyżej, z tym, że ostatni z nich ma postać \displaystyle s_m = 1.

Ćwiczenie 6

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

Wskazówka

"Naturalnym" przykładem języka akceptowanego przez automat ze stosem był język \displaystyle L=\{w\overleftarrow{w}, w \in A^*\}, gdyż stos działa w ten sposób, że elementy zdejmowane są z niego w odwrotnej kolejności niż były wkładane. Znajdź analogiczny "naturalny" przykład języka akceptowanego przez automat z kolejką. Zwróć uwagę, że w kolejce elementy wyjmowane są w takiej samej kolejności, w jakiej były do niej wkładane.

Rozwiązanie

Nie. Automat z kolejką akceptuje język \displaystyle L=\{ww, w \in  A^*\}, który nie jest akceptowany przez automat ze stosem.

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:

  1. \displaystyle L_5=\left\{ wc\overleftarrow{w} \in \{a,b,c\}^*: w \in \{ a,b\}^*  \right\},
  2. \displaystyle L_6=\left\{ wx\overleftarrow{w} \in \{a,b\}^*: x \in\{ a,b\}, w \in \{ a,b\}^*  \right\},
  3. \displaystyle L_7=\{a^{n}b^m \in \{a,b\}^*:\:  1\leqslant m\leqslant n\},
  4. \displaystyle L_8=\{a^{n}b^{m} \in \{a,b\}^*:\: m \neq n\}.

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