Automaty ze stosem

  1. 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\).

  2. 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\}\)

  3. Skonstruować automat ze stosem rozpoznający język

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

    Uogólnić tezę zadania.

  4. 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}})\).
  5. 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).

  6. 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?

  7. 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\}\)
  8. 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\)
  9. 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\ \}\).
  10. 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.
  11. 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.
  12. 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.

  13. 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}\}\).

  14. 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}\}\).