Automaty ze stosem

Skonstruować automaty ze stosem rozpoznające poznane wcześniej języki bezkontekstowe: zbiór palindromów, zbiór poprawnie uformowanych ciągów nawiasów, zbiór słów, które mają dwa razy więcej $b$ niż $a$, zbiór ciągów, które nie są postaci $ww$.
Dla liczby naturalnej $n$, niech $\mbox{bin}(n)\in\{ 0,1\}^{*}$ będzie binarnym przedstawieniem liczby $n$. Skonstruować automat ze stosem rozpoznający język

$\{\mbox{bin}(n)\,\$\,\mbox{bin}(n+1)^{R}\,:\, n\in N\}$
Skonstruować automat ze stosem rozpoznający język

$\{\mbox{bin}(n)\,\$\,\mbox{bin}(3*n)^{R}\,:\, n\in N\}$

Uogólnić tezę zadania.
Dowieść, że dla każdego automatu ze stosem $A$, można skonstruować automat ze stosem o dwóch stanach $A^{{\prime}}$, taki że $L(A)=L(A^{{\prime}})$.
Dowieść, że automatowi $A^{{\prime}}$ z poprzedniego zadania można postawić dalszy wymóg, że każde przejście jest postaci

$q,a,Z\,\rightarrow _{{A^{{\prime}}}}\, q^{{\prime}},\alpha$

gdzie $|\alpha|\leq 2$ ($q,q^{{\prime}}$ dowolne).
Dowieść, że dla każdego automatu ze stosem $A$, można skonstruować równoważny mu automat ze stosem $A^{{\prime\prime}}$, w którym każde przejście jest postaci push lub pop, tzn.

$q,a,Z\,\rightarrow _{{A^{{\prime\prime}}}}\, q^{{\prime}},YZ$

lub

$q,a,Z\,\rightarrow _{{A^{{\prime\prime}}}}\, q^{{\prime}},\epsilon$

Czy dla takich automatów można nadal ograniczyć liczbę stanów?
Mając dany automat ze stosem akceptujący język $L$, skonstruować automaty ze stosem akceptujące następujące języki:
1. $\mbox{Prefix}(L)=\{ w\,:\,(\exists v)wv\in L\}$
2. $\mbox{Suffix}(L)=\{ w\,:\,(\exists u)uw\in L\}$
3. $\mbox{Subword}(L)=\{ w\,:\,(\exists u,v)uwv\in L\}$
4. $L^{R}=\{ w^{R}\,:\, w\in L\}$
5. (*) $\mbox{Cycle}(L)=\{ vw\,:\, wv\in L\}$
Mając dany automat ze stosem akceptujący język $L$ i automat skończony akceptujący język $R$, skonstruować automaty ze stosem akceptujące następujące języki:
1. $LR^{{-1}}$
2. $R^{{-1}}L$
3. $L\cap R$
Niech $\# _{s}(w)$ oznacza liczbę symboli $s$ w słowie $w$, oraz $PREF(u)$ oznacza zbiór prefiksów słowa $u$. Ponadto oznaczmy przez $max(w),\ min(w),\ med(w)$ opowiednio maksimum, minimum i medianę liczb $\# _{a}(w),\# _{b}(w),\# _{c}(w)$.

Który z następujących języków jest regularny, a który bezkontekstowy?
1. $L_{1}\ =\ \{ u\in(a\cup b\cup c)^{*}\ :\ \forall\ w\in PREF(u)\ max(w)-min(w)\le 13\ \}$.
2. $L_{2}\ =\ \{ u\in(a\cup b\cup c)^{*}\ :\ \forall\ w\in PREF(u)\ max(w)-med(w)\le 13\ \}$.
Dla danych językow regularnych $L$ i $M$, skonstruować automat ze stosem rozpoznający język $\bigcup _{{i\in N}}(L^{i}\cap M^{i})$. Uwaga: ten zbiór nie musi być regularny.
Dowieść, że dla każdego automatu ze stosem $A$ istnieje stała $C$ (zależna od automatu), taka, że dla każdego słowa $w\in Z(A)$, istnieje obliczenie akceptujące (przez pusty stos) o długości $\leq C|w|$. Wskazówka: oszacować wysokość stosu w obliczeniu akceptującym.
Niech $A$ będzie automatem ze stosem. Dowieść, że zbiór słów, które są możliwymi zawartościami stosu automatu $A$, jest językiem regularnym. Formalnie, mamy na myśli zbiór

$\{\alpha\in\Gamma^{*}\,:\,(\exists w,v\in\Sigma^{*})(\exists q\in Q)\, q_{I},w,Z_{I}\,\vdash _{{A}}\, q,v,\alpha\}$

Wywnioskować stąd, że zbiór słów, które są możliwymi zawartościami stosu automatu $A$ w jakimś obliczeniu akceptującym, jest językiem bezkontekstowym.
Automat ze stosem $A=(\Sigma,\Gamma,Q,q_{I},Z_{I},\delta,F)$ nazywamy deterministycznym, jeśli w każdej sytuacji możliwy jest co najwyżej jeden ruch. Dokładniej:
1. jeśli, dla pewnej pary $q,Z$, zachodzi $q,\epsilon,Z\rightarrow _{A}p,\alpha$ przy pewnych $p,\alpha$, to dla żadnego $\sigma\in\Sigma$, nie zachodzi $q,\sigma,Z\rightarrow _{A}p^{{\prime}},\alpha^{{\prime}}$, dla żadnych
  $p^{{\prime}},\alpha^{{\prime}}$;
2. dla każdych $q,\sigma,Z$, istnieje co najwyżej jedna para $p,\alpha$, taka że $q,\sigma,Z\rightarrow _{A}p,\alpha$.
Język bezkontekstowy jest deterministyczny jeśli jest rozpoznawany przez pewien deterministyczny automat ze stosem (w sensie stanów akceptujących, tzn. $L=L(A)$).

Dowieść, że język $\{ a^{n}b^{n}:n\in{\bf N}\}$ $\cup$ $\{ a^{n}b^{{2n}}:n\in{\bf N}\}$ nie jest deterministycznym językiem bezkontekstowym.

Wskazówka. Zakładając, że istnieje deterministyczny automat $A$ rozpoznający ten język, rozważyć automat $A^{{\prime}}$, który różni się od $A$ tylko tym, że zamienia rolami $a$ i $b$. Przy pomocy tych dwóch automatów można łatwo skonstruować automat ze stosem rozpoznający język $\{ a^{n}b^{n}a^{n}:n\in{\bf N}\}$.
Wykazać, że zbiór palindromów nad alfabetem dwuelementowym nie jest deterministycznym językiem bezkontekstowym.

Wskazówka. Zastosować metodę z poprzedniego zadania. Przy pomocy hipotetycznego automatu deterministycznego rozpoznającego palindromy można np. skonstruować automat rozpoznający język $\{ ca^{n}ba^{n}ca^{n}ba^{n}c:n\in{\bf N}\}$.