J_{}ezyki, Automaty i Obliczenia 1996

Zadania z gwiazdk _{}a

1. Skonstruować nieskończony ci _{}ag liter nad alfabetem {a, b, c} nie zawieraj _{}acy żadnego kwadratu, tj. podsłowa postaci ww, w ≠ ϵ.

Termin rozwi _{}azania : do 23. X. 1996.

2. Niech L b_{}edzie j_{}ezykiem regularnym. Dowieść, że nast_{}epuj _{}acy j_{}ezyk jest również regularny : Fibb(L) = {w : (∃u)|u| = F_{|w|} ∧ wu ∈ L} gdzie F_{n} jest n-t _{}a liczb _{}a Fibonacciego tzn.

F_{1} = F_{2} = 1
F_{n+2} = F_{n} + F_{n+1}

Termin rozwi _{}azania : do 30. X. 1996.

3. Słowo nad alfabetem jednoliterowym można utożsamić z jego długości _{}a. Zatem j_{}ezyk nad takim alfabetem można utożsamić ze zbiorem liczb naturalnych. Dowieść, że zbiór liczb naturalnych jest regularny wtedy i tylko wtedy, gdy można go przedstawić jako sum_{}e skończonej liczby zbiorów postaci {a + b · n | n ∈ N} (taki zbiór nazywa si_{}e semi–liniowym).

Termin rozwi _{}azania : do 30. X. 1996.

4. Niech A – alfabet, A′ = {a′ : a ∈ A}. Określamy homomorfizmy h, h_{1}, h_{2} z A ∪ A′ w A nast_{}epuj _{}aco: h(a) = h(a′) = a, h_{1}(a) = a, h_{1}(a′) = ϵ, h_{2}(a) = ϵ, h_{2}(a′) = a.

Definiujemy przeplot j_{}ezyków L_{1} i L_{2} :

Shuffle(L_{1}, L_{2}) = {x : (∃y ∈ h^{−1}(x))h_{1}(y) ∈ L_{1} ∧ h_{2}(y) ∈ L_{2}}

Niech Σ = Σ′ ∪ Σ′′, gdzie Σ′ ∩ Σ′′ = ∅. Zaprojektować algorytm, który, dla danego automatu skończonego A nad alfabetem Σ, rozstrzyga, czy L(A) = Shuffle(L_{1}, L_{2}), dla pewnych L_{1} ⊆ Σ′^{∗} i L_{2} ⊆ Σ′′^{∗}.

Termin rozwi _{}azania : do 6. XI. 1996.

5. Dowieść, że dla dowolnego słowa w ∈ Σ^{∗}, można skonstruować automat deterministyczny rozpoznaj _{}acy zbiór wszystkich podsłów słowa w, w taki sposób, że liczba stanów automatu zależy liniowo od długości słowa w.

Termin rozwi _{}azania : do 6. XI. 1996.

6. Dowieść, że nad jednoliterowym alfabetem każdy j_{}ezyk bezkontekstowy jest regularny.

Termin rozwi _{}azania : do 27. XI. 1996.

7. Dowieść, że dla ustalonego automatu ze stosem, zbiór słów, które stanowi _{}a zawartość stosu w pewnym obliczeniu akceptuj _{}acym jest j_{}ezykiem bezkontekstowym. Wskazówka : dowieść najpierw, że zbiór słów, które stanowi _{}a zawartość stosu w jakimś obliczeniu, jest regularny.

Czy pierwszy ze wspomnianych zbiorów jest również zawsze j_{}ezykiem regularnym ?

Termin rozwi _{}azania : do 27. XI. 1996.

8. Dowieść, że j_{}ezyk {ww^{R} : w ∈ {0, 1}^{∗}} nie jest postaci L(A) dla żadnego deterministycznego automatu ze stosem.

Automat ze stosem jest deterministyczny, jeśli, dla każdych q, a, Z, istnieje co najwyżej jedno przejście postaci q, a, Z →_{A} q′, γ.

Termin rozwi _{}azania : do 27. XI. 1996.

9. Rozważamy wyrażenia Boole’owskie zbudowane ze stałych 0, 1, nawiasów (,) i operacji ∧ i ∨, z oczywist _{}a semantyk _{}a. Czy istnieje automat skończony nad alfabetem {0, 1, (,), ∧, ∨} który, po przeczytaniu takiego wyrażenia Boole’owskiego przyjmuje stan akceptuj _{}acy wtedy i tylko wtedy, gdy wyrażenie ma wartość 1 ?

Uwaga : nie ż _{}adamy, by automat rozpoznawał również struktur_{}e wyrażeń; tzn. nasz automat może również akceptować wiele słów nie b_{}ed _{}acych wyrażeniami Boole’owskimi (jak np. )))1∨ ).

Termin rozwi _{}azania : do 27. XI. 1996.

10. Dowieść, że jeżeli j_{}ezyk bezkontekstowy L ma tak _{}a własność, że dla każdych w, v ∈ L, w jest prefiksem v lub v jest prefiksem w, to L jest regularny.

Termin rozwi _{}azania : do 27. XI. 1996.