Języki, automaty i obliczenia/Ćwiczenia 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne

{Automat ze stosem.Gramatyki bezkontekstowe i automaty ze stosem.}

ĆWICZENIA 11

Ćwiczenie

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 $L$ jest deterministyczny?

1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_1=\{a^{n}b^{n+m}a^{m}:\: m,n\geq 1\} }
2. $L_2=\{w\overleftarrow{w}:w\in \{a,b{\}}^{*}\}$
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_3=\{a^{n}b^m:\: 1\leq n\leq m\} }
4. $L_4=\{w\in \{a,b{\}}^{+}:{\mathrm{\#}}_{a}w={\mathrm{\#}}_{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

rys 1 ja-lekcja11-c-rys1

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.
Szukany automat określony jest rysunkiem

rys 2 ja-lekcja11-c-rys2

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 Uzupelnic 1|.
ROZWIĄZANIE punktu 3. Szukany automat określony jest rysunkiem

rys 3 ja-lekcja11-c-rys3

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. Szukany automat określony jest rysunkiem

rys 4 ja-lekcja11-c-rys4

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

Napisz na podstawie dowodu twierdzenia Uzupelnic lekcja11-w twas-bk|

1. algorytm konstrukcji automatu ze stosem

rozpoznającego język generowany przez daną gramatykę bezkontekstową w postaci normalnej Greibach,

1. algorytm konstrukcji gramatyki bezkontekstowej generującej język rozpoznawany przez pusty stsos

przez dany automat ze stsosem.

Ćwiczenie

Wykorzystując algorytmy z poprzedniego zadania określ

1. 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$

1. gramatykę generującą język akceptowany przez pusty stos przez automat zadany rysunkiem
   

rys5 ja-lekcja11-c-rys5

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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\{a^{n}b^n:\: 1\leq 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

rys6 ja-lekcja11-c-rys6

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

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\ge 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|\le k\}$, $F=S_F\times T$,
$\mathrm{\forall }s,s^{\prime }\in S,\mathrm{\forall }z\in A_S,\mathrm{\forall }u,v\in A_S^{*},\mathrm{\forall }a\in A\cup \{1\}$

$f((s,uz),a)=\{(s^{\prime },uv):(uz,s)|{⟹}^a(uv,s^{\prime })\}$

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

Ćwiczenie

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.

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 $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 \left\{1\right\})⟶{{𝒫}}_{sk}(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\ge 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=au$ oraz $s_{i+1}=ub$ 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

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\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 $L=\{ww,w\in A^{*}\}$, który nie jest akceptowany przez automat ze stosem.

ZADANIA DOMOWE

Ćwiczenie

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. $L_5=\{wc\overleftarrow{w}\in \{a,b,c{\}}^{*}:w\in \{a,b{\}}^{*}\}$
2. $L_6=\{wx\overleftarrow{w}\in \{a,b{\}}^{*}:x\in \{a,b\},w\in \{a,b{\}}^{*}\}$
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_7=\{a^{n}b^m \in \{a,b\}^*:\: 1\leq m\leq n\} }
4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_8=\{a^{n}b^{m} \in \{a,b\}^*:\: m \neq n\} }

Ćwiczenie

Określ automat ze stosem, który rozpoznaje język Łukasiewicza zapisany w wersji postfiksowej (Uzupelnic lekcja11-w luk|)