|
|
| Linia 1: |
Linia 1: |
| {Automat ze stosem.Gramatyki bezkontekstowe i automaty ze stosem.}
| |
|
| |
|
| ==ĆWICZENIA 11==
| |
|
| |
| {{cwiczenie|||
| |
| 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ęzyk <math>\displaystyle L</math> jest deterministyczny?
| |
| # <math>\displaystyle L_1=\{a^{n}b^{n+m}a^{m}:\: m,n\geq 1\} </math>
| |
| # <math>\displaystyle L_2=\left\{ w\overleftarrow{w} : w \in \{ a,b\}^* \right\} </math>
| |
| # <math>\displaystyle L_3=\{a^{n}b^m:\: 1\leq n\leq m\} </math>
| |
| # <math>\displaystyle L_4=\{w \in \{ a,b\}^+ :\#_a w = \#_b w \} </math>
| |
|
| |
| }}
| |
|
| |
| 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 <br>
| |
|
| |
| rys 1 ja-lekcja11-c-rys1 <br>
| |
|
| |
| gdzie <math>\displaystyle A_S = \{z_0,a,b\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu.
| |
| Zauważ, że automat ten akceptuje język <math>\displaystyle L_1</math> zarówno przez stany końcowe jak i przez pusty stos.
| |
| Automat jest deterministyczny, a to oznacza, że język <math>\displaystyle L_1</math> jest też deterministyczny.<br>
| |
| ROZWIĄZANIE punktu 2.<br>
| |
| Szukany automat określony jest rysunkiem <br>
| |
|
| |
| rys 2 ja-lekcja11-c-rys2 <br>
| |
|
| |
| gdzie <math>\displaystyle A_S = \{z_0,a,b\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu i akceptuje język <math>\displaystyle L_2</math> przez pusty stos.
| |
| Automat jest niedeterministyczny i język <math>\displaystyle L_2</math> 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 <math>\displaystyle L_5</math> i <math>\displaystyle L_6</math>
| |
| z ćwiczenia [[##1|Uzupelnic 1|]].<br>
| |
| ROZWIĄZANIE punktu 3. Szukany automat określony jest rysunkiem <br>
| |
|
| |
| rys 3 ja-lekcja11-c-rys3 <br>
| |
|
| |
| gdzie <math>\displaystyle A_S = \{z_0,a\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu. Automat ten akceptuje język <math>\displaystyle L_3</math>
| |
| przez stany końcowe i jest automatem deterministycznym.
| |
|
| |
| ROZWIĄZANIE punktu 4. Szukany automat określony jest rysunkiem <br>
| |
|
| |
| rys 4 ja-lekcja11-c-rys4 <br>
| |
|
| |
| gdzie <math>\displaystyle A_S = \{z_0,a,b \}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu. Automat akceptuje język <math>\displaystyle L_4</math>
| |
| przez stany końcowe i jest automatem niedeterministycznym. Uzasadnij ten fakt. Czy język <math>\displaystyle L_4</math> jest językiem
| |
| niedeterministycznym?
| |
|
| |
| {{cwiczenie|||
| |
| Napisz na podstawie dowodu twierdzenia [[##lekcja11-w twas-bk|Uzupelnic lekcja11-w twas-bk|]]
| |
| # 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 stsos
| |
| przez dany automat ze stsosem.
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Wykorzystując algorytmy z poprzedniego zadania określ
| |
| # automat akceptujący język generowany przez gramatykę <math>\displaystyle G</math> o zbiorze praw <br>
| |
| <math>\displaystyle P : v_0 \rightarrow av_0 v_1 \;| \; av_1, v_1 \rightarrow b</math>
| |
| # gramatykę generującą język akceptowany przez pusty stos przez automat zadany rysunkiem <br>
| |
|
| |
| rys5 ja-lekcja11-c-rys5 <br>
| |
|
| |
| gdzie <math>\displaystyle A_S = \{z_0,a\}</math>, a <math>\displaystyle z_0</math> jest symbolem początkowym stosu.
| |
|
| |
| }}
| |
|
| |
| ROZWIĄZANIE. Zarówno w punkcie 1 jak i 2 rozważanym językiem jest <math>\displaystyle L=\{a^{n}b^n:\: 1\leq n\} </math> .<br>
| |
| Punkt 1.
| |
| Gramatyka jest w postaci Greibach i możemy od razu określić automat.
| |
| Zgodnie z konstrukcją jest to automat jednostanowy zadany rysunkiem <br>
| |
|
| |
| rys6 ja-lekcja11-c-rys6 <br>
| |
|
| |
| gdzie <math>\displaystyle A_S = \{v_0,v_1,a,b\}</math>, a <math>\displaystyle v_0</math> jest symbolem początkowym stosu. <br>
| |
| Dla przykładu prześledźmy akceptację przez ten automat słowa <math>\displaystyle a^2b^2</math>.<br>
| |
| <math>\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)</math><br>
| |
|
| |
| Punkt 2.<br>
| |
| Gramatykę zdefiniujemy przez podanie zbioru praw wskazując równocześnie z jakiego przejścia w automacie
| |
| dane prawo powstało.<br>
| |
| <math>\displaystyle v_0\rightarrow (q_0,z_0,q_1)</math><br>
| |
| <math>\displaystyle (q_0,z_0,q_1) \rightarrow a (q_0,a,q_1) \longleftrightarrow (z_0,q_0,a)|\!\!\!\Longrightarrow(a,q_0)</math><br>
| |
| <math>\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)</math><br>
| |
| <math>\displaystyle (q_0,a,q_1)\rightarrow b\longleftrightarrow (a,q_0,b) |\!\!\!\Longrightarrow (1,q_1) </math><br>
| |
| <math>\displaystyle (q_1,a,q_1) \rightarrow b \longleftrightarrow (a,q_1,b) |\!\!\!\Longrightarrow (1,q_1)</math><br>
| |
|
| |
| Zauważmy, że w obu konstrukcjach otrzymujemy gramatykę i automat różne od wyjściowych.
| |
|
| |
| {{cwiczenie|||
| |
| 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. <br>
| |
| }}
| |
|
| |
| 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 <math>\displaystyle k\geq 1</math> będzie dowolną stałą, a <math>\displaystyle \mathcal{A}_S=(S,A,A_S,f_S,s_0,z_0,S_F)</math>
| |
| automatem, w którym wielkość stosu ograniczona jest przez stałą <math>\displaystyle k</math>. Równoważny automat skończenie stanowy jest automatem
| |
| niedeterministycznym z pustymi przejściami.<br>
| |
| Niech <math>\displaystyle \mathcal{A}=(S\times T,A,f,(s_0,z_0),F)</math>, gdzie <math>\displaystyle T=\{w \in A_s^*: |w|\leq k\}</math>, <math>\displaystyle F=S_F\times T</math>,<br>
| |
| <math>\displaystyle \forall s,s' \in S, \forall z \in A_S, \forall u,v \in A^*_S, \forall a \in A \cup \{1\} </math>
| |
| <center><math>\displaystyle f((s,uz),a)=\{(s',uv): (uz,s) |\!\!\!\Longrightarrow^a (uv,s')\} </math></center>
| |
|
| |
| Co zmieni się w definiowanym automacie skończenie stanowym, jeśli automat ze stosem będzie akceptował przez pusty stos?
| |
|
| |
| {{cwiczenie|||
| |
| 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 (być może
| |
| 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 <math>\displaystyle A
| |
| </math> nazywamy system <math>\displaystyle \mathcal{AK}=(Q,A,A_{K},f,s_{0},z_{0},Q_{F}) </math> , w którym<br>
| |
| <math>\displaystyle A </math> - jest alfabetem, <math>\displaystyle A_{K} </math> - jest dowolnym
| |
| skończonym i niepustym zbiorem zwanym alfabetem kolejki
| |
| (niekoniecznie rozłącznym z <math>\displaystyle A </math> ), <math>\displaystyle Q </math> - jest dowolnym,
| |
| skończonym i niepustym zbiorem zwanym zbiorem stanów, <math>\displaystyle f:A_{K}\times Q\times (A\cup \left\{ 1\right\} )\longrightarrow
| |
| \mathcal{P}_{sk}(A_{K}^{*}\times Q) </math> jest funkcją przejść, której
| |
| wartościami są skończone podzbiory <math>\displaystyle A_{K}^{*}\times Q </math> (także
| |
| zbiór pusty), <math>\displaystyle q_{0}\in Q </math> jest stanem początkowym, <math>\displaystyle z_{0}\in
| |
| A_{K} </math> symbolem początkowym kolejki, <math>\displaystyle Q_{F}\subset Q </math> zbiorem
| |
| stanów końcowych.
| |
|
| |
| ROZWIĄZANIE punktu 2.
| |
|
| |
| Automat z kolejką <math>\displaystyle \mathcal{AK}=(Q,A,A_{K},f,s_{0},z_{0},Q_{F})</math>
| |
| akceptuje przez stan końcowy słowo <math>\displaystyle w=w_1w_2...w_m \in A^*</math> (<math>\displaystyle w_1,
| |
| w_2, ..., w_m \in A, m \geq 0</math>), jeśli istnieje sekwencja stanów
| |
| <math>\displaystyle r_0, r_1, ..., r_m</math> oraz słów <math>\displaystyle s_0, s_1,
| |
| ..., s_m \in A_{K}^*</math> takich, że:
| |
| * <math>\displaystyle r_0 = q_0</math>,
| |
| * <math>\displaystyle s_0 = z_0</math>,
| |
| * <math>\displaystyle (r_{i+1},b) \in f(r_i, w_{i+1}, a)</math>, gdzie <math>\displaystyle s_i=au</math> oraz <math>\displaystyle s_{i+1} = ub</math> dla pewnego <math>\displaystyle u \in A_{K}^*</math>,
| |
| * <math>\displaystyle r_m \in Q_{F}</math>.
| |
|
| |
| Automat akceptuje słowo <math>\displaystyle w</math> przez pustą kolejkę przy takich samych
| |
| warunkach jak powyżej, z tym że ostatni z nich ma postać <math>\displaystyle s_m = 1</math>.
| |
|
| |
| {{cwiczenie|||
| |
| 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 <math>\displaystyle L=\{w\overleftarrow{w}, w \in A^*\}</math>, 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 <math>\displaystyle L=\{ww, w \in
| |
| A^*\}</math>, który nie jest akceptowany przez automat ze stosem.
| |
|
| |
| ZADANIA DOMOWE
| |
|
| |
| {{cwiczenie|||
| |
|
| |
| 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.
| |
| # <math>\displaystyle L_5=\left\{ wc\overleftarrow{w} \in \{a,b,c\}^*: w \in \{ a,b\}^* \right\} </math>
| |
| # <math>\displaystyle L_6=\left\{ wx\overleftarrow{w} \in \{a,b\}^*: x \in\{ a,b\}, w \in \{ a,b\}^* \right\} </math>
| |
| # <math>\displaystyle L_7=\{a^{n}b^m \in \{a,b\}^*:\: 1\leq m\leq n\} </math>
| |
| # <math>\displaystyle L_8=\{a^{n}b^{m} \in \{a,b\}^*:\: m \neq n\} </math>
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|||
| |
| Określ automat ze stosem, który rozpoznaje język Łukasiewicza zapisany w wersji postfiksowej ([[##lekcja11-w luk|Uzupelnic lekcja11-w luk|]])
| |
|
| |
| }}
| |
