Processing math: 100%
Strona główna › Języki, automaty i obliczenia - zbiór zadań

Automaty ze stosem

pon., 03/21/2011 - 14:37 — ciebie

  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 bin(n)∈{0,1}∗ będzie binarnym przedstawieniem liczby n. Skonstruować automat ze stosem rozpoznający język

    {bin(n)$bin(n+1)R:n∈N}

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

    {bin(n)$bin(3∗n)R:n∈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′, taki że L(A)=L(A′).
  5. Dowieść, że automatowi A′ z poprzedniego zadania można postawić dalszy wymóg, że każde przejście jest postaci

    q,a,Z→A′q′,α

    gdzie |α|≤2 (q,q′ dowolne).

  6. Dowieść, że dla każdego automatu ze stosem A, można skonstruować równoważny mu automat ze stosem A′′, w którym każde przejście jest postaci push lub pop, tzn.

    q,a,Z→A′′q′,YZ

    lub

    q,a,Z→A′′q′,ϵ

    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. Prefix(L)={w:(∃v)wv∈L}
    2. Suffix(L)={w:(∃u)uw∈L}
    3. Subword(L)={w:(∃u,v)uwv∈L}
    4. LR={wR:w∈L}
    5. (*) Cycle(L)={vw:wv∈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−1L
    3. L∩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. L1 = {u∈(a∪b∪c)∗ : ∀ w∈PREF(u) max(w)−min(w)≤13 }.
    2. L2 = {u∈(a∪b∪c)∗ : ∀ w∈PREF(u) max(w)−med(w)≤13 }.
  10. Dla danych językow regularnych L i M, skonstruować automat ze stosem rozpoznający język ⋃i∈N(Li∩Mi). 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∈Z(A), istnieje obliczenie akceptujące (przez pusty stos) o długości ≤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

    {α∈Γ∗:(∃w,v∈Σ∗)(∃q∈Q)qI,w,ZI⊢Aq,v,α}

    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=(Σ,Γ,Q,qI,ZI,δ,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,ϵ,Z→Ap,α przy pewnych p,α, to dla żadnego σ∈Σ, nie zachodzi q,σ,Z→Ap′,α′, dla żadnych
      p′,α′;

    2. dla każdych q,σ,Z, istnieje co najwyżej jedna para p,α, taka że q,σ,Z→Ap,α.

    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 {anbn:n∈N} ∪ {anb2n:n∈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′, 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 {anbnan:n∈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 {canbancanbanc:n∈N}.