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

Ć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 $L_{i}$ są deterministyczne?

$L_{1} = {a^{n} b^{n + m} a^{m} : : m, n ⩾ 1},$
$L_{2} = {w \overset{\leftarrow}{w} : w \in {a, b}^{*}},$
$L_{3} = {a^{n} b^{m} : : 1 ⩽ n ⩽ m},$
$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

gdzie $A_{S} = {z_{0}, a, b}$ , a $z_{0}$ jest symbolem początkowym stosu. Zauważ, że automat ten akceptuje język $L_{1}$ zarówno przez stany końcowe jak i przez pusty stos. Automat jest deterministyczny, a to oznacza, że język $L_{1}$ jest też deterministyczny.

Rozwiązanie punktu 2

gdzie $A_{S} = {z_{0}, a, b}$ , a $z_{0}$ jest symbolem początkowym stosu i akceptuje język $L_{2}$ przez pusty stos. Automat jest niedeterministyczny i język $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 $L_{5}$ i $L_{6}$ z ćwiczenia 1.

Rozwiązanie punktu 3

gdzie $A_{S} = {z_{0}, a}$ , a $z_{0}$ jest symbolem początkowym stosu. Automat ten akceptuje język $L_{3}$ przez stany końcowe i jest automatem deterministycznym.

Rozwiązanie punktu 4

gdzie $A_{S} = {z_{0}, a, b}$ , a $z_{0}$ jest symbolem początkowym stosu. Automat akceptuje język $L_{4}$ przez stany końcowe i jest automatem niedeterministycznym. Uzasadnij ten fakt. Czy język $L_{4}$ jest językiem niedeterministycznym?

Ćwiczenie 2

Napisz na podstawie dowodu twierdzenia 2.2

algorytm konstrukcji automatu ze stosem rozpoznającego język generowany przez daną gramatykę bezkontekstową w postaci normalnej Greibach,
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:

automat akceptujący język generowany przez gramatykę $G$ o zbiorze praw
$P : v_{0} \to a v_{0} v_{1} | a v_{1}, v_{1} \to b$ ,
gramatykę generującą język akceptowany przez pusty stos przez automat zadany rysunkiem:

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

<div.thumbcaption>Rysunek 5

gdzie $A_{S} = {z_{0}, a}$ , a $z_{0}$ jest symbolem początkowym stosu.

Rozwiązanie

Zarówno w punkcie 1 jak i 2 rozważanym językiem jest $L = {a^{n} b^{n} : : 1 ⩽ 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>

<div.thumbcaption>Rysunek 6

gdzie $A_{S} = {v_{0}, v_{1}, a, b}$ , a $v_{0}$ jest symbolem początkowym stosu.
Dla przykładu prześledźmy akceptację przez ten automat słowa $a^{2} b^{2}$ .
$(v_{0}, q) | ⟹ (v_{1} v_{0} a, q) | ⟹^{a} (v_{1} v_{0}, q) | ⟹ (v_{1} v_{1} a, q) | ⟹^{a} (v_{1} v_{1}, q) | ⟹ (v_{1} b, q) | ⟹^{b} (v_{1}, q) | ⟹^{b} (b, q) | ⟹^{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:
$v_{0} \to (q_{0}, z_{0}, q_{1})$
$(q_{0}, z_{0}, q_{1}) \to a (q_{0}, a, q_{1}) ⟷ (z_{0}, q_{0}, a) | ⟹ (a, q_{0})$
$(q_{0}, a, q_{1}) \to a (q_{0}, a, q_{1}) (q_{1}, a, q_{1}) ⟷ (a, q_{0}, a) | ⟹ (a^{2}, q_{0})$
$(q_{0}, a, q_{1}) \to b ⟷ (a, q_{0}, b) | ⟹ (1, q_{1})$
$(q_{1}, a, q_{1}) \to b ⟷ (a, q_{1}, b) | ⟹ (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 $k ⩾ 1$ będzie dowolną stałą, a $𝒜_{S} = (S, A, A_{S}, f_{S}, s_{0}, z_{0}, S_{F})$ automatem, w którym wielkość stosu ograniczona jest przez stałą $k$ . Równoważny automat skończenie stanowy jest automatem niedeterministycznym z pustymi przejściami.
Niech $𝒜 = (S \times T, A, f, (s_{0}, z_{0}), F)$ , gdzie $T = {w \in A_{s}^{*} : | w | ⩽ k}$ , $F = S_{F} \times T$ ,
$\forall s, s^{'} \in S, \forall z \in A_{S}, \forall u, v \in A_{S}^{*}, \forall a \in A \cup {1}$

f ((s, u z), a) = {(s^{'}, u v) : (u z, s) | ⟹^{a} (u v, 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.

Podaj formalną definicję automatu z kolejką.
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 $A$ nazywamy system $𝒜 𝒦 = (Q, A, A_{K}, f, s_{0}, z_{0}, Q_{F})$ , w którym
$A$ - jest alfabetem, $A_{K}$ - jest dowolnym skończonym i niepustym zbiorem zwanym alfabetem kolejki (niekoniecznie rozłącznym z $A$ ), $Q$ - jest dowolnym, skończonym i niepustym zbiorem zwanym zbiorem stanów, $f : A_{K} \times Q \times (A \cup {1}) ⟶ 𝒫_{s k} (A_{K}^{*} \times Q)$ jest funkcją przejść, której wartościami są skończone podzbiory $A_{K}^{*} \times Q$ (także zbiór pusty), $q_{0} \in Q$ jest stanem początkowym, $z_{0} \in A_{K}$ symbolem początkowym kolejki, $Q_{F} \subset Q$ zbiorem stanów końcowych.

Rozwiązanie punktu 2

Automat z kolejką $𝒜 𝒦 = (Q, A, A_{K}, f, s_{0}, z_{0}, Q_{F})$ akceptuje przez stan końcowy słowo $w = w_{1} w_{2} . . . w_{m} \in A^{*}$ ( $w_{1}, w_{2}, . . ., w_{m} \in A, m ⩾ 0$ ), jeśli istnieje sekwencja stanów $r_{0}, r_{1}, . . ., r_{m}$ oraz słów $s_{0}, s_{1}, . . ., s_{m} \in A_{K}^{*}$ takich, że:

$r_{0} = q_{0}$ ,
$s_{0} = z_{0}$ ,
$(r_{i + 1}, b) \in f (r_{i}, w_{i + 1}, a)$ , gdzie $s_{i} = a u$ oraz $s_{i + 1} = u b$ dla pewnego $u \in A_{K}^{*}$ ,
$r_{m} \in Q_{F}$ .

Automat akceptuje słowo $w$ przez pustą kolejkę przy takich samych warunkach jak powyżej, z tym, że ostatni z nich ma postać $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 $L = {w \overset{\leftarrow}{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 $L = {w w, 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:

$L_{5} = {w c \overset{\leftarrow}{w} \in {a, b, c}^{*} : w \in {a, b}^{*}},$
$L_{6} = {w x \overset{\leftarrow}{w} \in {a, b}^{*} : x \in {a, b}, w \in {a, b}^{*}},$
$L_{7} = {a^{n} b^{m} \in {a, b}^{*} : : 1 ⩽ m ⩽ n},$
$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)

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

Ćwiczenia 11

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia