Jȩzyki, Automaty i Obliczenia

Zadania

Czȩść druga

Damian Niwiński i Wojciech Rytter

Styczeń 2005

1 J_{}ezyki bezkontekstowe

1.1 Gramatyki bezkontekstowe

1. Podać gramatyki bezkontekstowe generuj _{}ace nast_{}epuj _{}ace j_{}ezyki:

(a) zbiór słów nad alfabetem {a, b}, które zawieraj _{}a tyle samo a co b;

(b) zbiór słów nad alfabetem {a, b}, które zawieraj _{}a dwa razy wi_{}ecej a niż b;

(c) zbiór słów nad alfabetem {a, b} o długości parzystej, w których liczba wyst _{}apień litery b na pozycjach parzystych jest równa liczbie wyst _{}apień tej litery na pozycjach nieparzystych;

(d) zbiór wyrażeń arytmetycznych nad alfabetem {0, 1, (,), +, ·}, które, przy zwykłej interpretacji działań dla liczb naturalnych, maj _{}a wartość 3;

(e) zbiór wyrażeń arytmetycznych w notacji polskiej (nad alfabetem {0, 1, +, ·}) o wartości 4;

(f) zbiór poprawnie zbudowanych formuł rachunku zdań ze zmiennymi zdaniowymi p, q i stałymi logicznymi 0, 1 (alfabet: {p, q, 0, 1, ∧, ∨, ⇒, ¬});

(g) zbiór formuł rachunku zdań bez zmiennych, o wartości logicznej “prawda”;

(h) {a^{i}b^{j}c^{k} : i ≠ j ∨ j ≠ k};

(i) {a^{i}b^{j}a^{k} : i + k = j}.

2. Dla danych gramatyk bezkontekstowych G, H, skonstruować gramatyki generuj _{}ace j_{}ezyki L(G) ∪ L(H), L(G)L(H), (L(G))^{∗}, (L(G))^{R} (=lustrzane odbicie).

3. Wykazać, że zbiór palindromów nad ustalonym alfabetem jak również jego dopełnienie s _{}a j_{}ezykami bezkontekstowymi.

4. Skonstruować gramatyk_{}e bezkontekstow _{}a z jednym symbolem nieterminalnym generuj _{}ac _{}a zbiór {x ∈ (a+b)^{∗} : #_{a}(x) = #_{b}(x) }, gdzie #_{s}(w) oznacza liczb_{}e wyst _{}apień symbolu s w słowie w.

5. Dowieść, że nast_{}epuj _{}ace warunki s _{}a równoważne dla j_{}ezyka L ⊆ Σ^{∗}:

(a) L jest regularny,

(b) L jest generowany przez gramatyk_{}e bezkontekstow _{}a, w której każda reguła jest postaci X → ϵ, X → Y, lub X → σY, σ ∈ Σ,

(c) L jest generowany przez gramatyk_{}e bezkontekstow _{}a, w której każda reguła jest postaci X → ϵ, X → Y, lub X → Y σ, σ ∈ Σ,

(d) L jest generowany przez gramatyk_{}e bezkontekstow _{}a, w której każda reguła jest postaci X → α lub X → βY, α, β ∈ Σ^{∗}.

6. Podać przykład gramatyki bezkontekstowej w której każda reguła jest postaci X → ϵ, X → Y, X → σY lub X → Y σ, σ ∈ Σ, ale j_{}ezyk generowany przez gramatyk_{}e nie jest regularny.

7. Czy każdy j_{}ezyk bezkontekstowy jest generowany przez gramatyk_{}e w postaci z poprzedniego zadania?

8. Powiemy, że gramatyka G ma własność właściwego samozap_{}etlenia, jeśli dla pewnej zmiennej X zachodzi X →^{G}^{∗} αXβ, gdzie α, β ≠ ϵ. Udowodnij, że gramatyka bezkontekstowa nie maj _{}aca własności właściwego samozap_{}etlenia generuje j_{}ezyk regularny.

9. Udowodnij, że każdy j_{}ezyk bezkontekstowy nad jednoliterowym alfabetem jest regularny.

10. Udowodnij, że jeśli L jest bezkontekstowy to j_{}ezyk {a^{|w|} : w ∈ L} jest regularny.

11. Niech G b_{}edzie gramatyk _{}a bezkontekstow _{}a, z m zmiennymi i niech, dla każdej reguły Y →^{G} w, |w| ≤ ℓ. Dowieść, że jeśli X_{I} →^{G∗} ϵ, to istnieje wyprowadzenie o długości 1 + ℓ + ℓ^{2} + … + ℓ^{m−1}. Czy to oszacowanie jest optymalne?

12. Dowieść, że dla każdej gramatyki G istnieje stała C, taka, że dla dowolnego w ≠ ϵ, jeśli X_{I} →^{G∗} w, to istnieje wyprowadzenie o długości ≤ C · |w|.

13. Załóżmy, że mamy pewn _{}a skończon _{}a liczb_{}e reguł wymazuj _{}acych postaci α → ϵ. Stosuj _{}ac takie reguły możemy w danym słowie zast_{}epować słowo α przez słowo puste. Niech L b_{}edzie zbiorem słów, które możemy przekształcić na słowo puste stosuj _{}ac reguły wymazywania.

Czy zawsze istnieje gramatyka bezkontekstowa generuj _{}aca L i maj _{}aca tylko jeden symbol nieterminalny ?

14. Zaprojektować algorytm, który, dla danej gramatyki G, odpowiada na pytanie, czy j_{}ezyk L(G) jest nieskończony.

15. Udowodnij, że każdy j_{}ezyk bezkontekstowy może być generowany przez gramatyk_{}e w której każdy symbol nieterminalny (poza być może symbolem pocz _{}atkowym) generuje nieskończenie wiele słów terminalnych.

1.2 Bezkontekstowy czy nie ? — lematy o pompowaniu

1. Udowodnić, że żaden nieskończony podzbiór j_{}ezyka L = {a^{n}b^{n}c^{n} : n ≥ 1} nie jest j_{}ezykiem bezkontekstowym.

2. Udowodnić, że dopełnienie j_{}ezyka z poprzedniego zadania jest j_{}ezykiem bezkontekstowym.

3. Udowodnić, że jeśli alfabet Σ ma co najmniej dwie litery, to j_{}ezyk L = {ww : w ∈ Σ^{∗}} nie jest bezkontekstowy, natomiast jego dopełnienie Σ^{∗} − L jest j_{}ezykiem bezkontekstowym.

4. Udowodnić, że j_{}ezyk L = {xcx : x ∈ (a+b)^{∗} } nie jest j_{}ezykiem bezkontekstowym.

5. Udowodnić, że dopełnienie j_{}ezyka z poprzedniego zadania jest j_{}ezykiem bezkontekstowym.

6. Pokazać, że j_{}ezyk dopasowywania wzorca L = {xcy : x, y ∈ (a + b)^{∗}, y ∈ Subwords(x)} nie jest bezkontekstowy. Czy dopelnienie tego j_{}ezyka jest bezkontekstowe ?

7. Pokazać, że j_{}ezyk L = {xcy^{R} : x, y ∈ (a + b)^{∗}, y ∈ Subwords(x)} jest bezkontekstowy.

8. (*) Pokazać, że dopełnienie j_{}ezyka z poprzedniego zadania nie jest j_{}ezykiem bezkontekstowym.

9. Udowodnić, że j_{}ezyk L = {a^{i}b^{j}c^{k} : i ≠ j, i ≠ k, j ≠ k } nie jest bezkontekstowy. Czy jego dopełnienie jest bezkontekstowe ?

10. Czy j_{}ezyk L = {a^{i}b^{j}a^{i}b^{j} : i, j ≥ 1 } jest bezkontekstowy ?

Czy jego dopełnienie jest j_{}ezykiem bezkontekstowym ?

11. Udowodnić, że j_{}ezyk L = {ww^{R}w : w ∈ (a + b)^{∗}} nie jest bezkontekstowy. Czy jego dopełnienie jest bezkontekstowe ?

12. Pokaż, że j_{}ezyk {x#y^{R} : x, y ∈ {0, 1}^{+}, [x]_{2} + 1 = [y]_{2}} jest bezkontekstowy.

13. Pokaż, że j_{}ezyk {x#y : x, y ∈ {0, 1}^{+}, [x]_{2} + 1 = [y]_{2}} nie jest bezkontekstowy.

14. Które z nast_{}epuj _{}acych j_{}ezyków s _{}a bezkontekstowe ?

(a) {a^{m}b^{n} : m < n < 2m}

(b) (a + b)^{∗} − {(a^{n}b^{n})^{n} : n ≥ 1}

(c) {ww^{R}w : w ∈ (a + b)^{∗}}

(d) {a^{x}ba^{y}ba^{z} : x + y = z}

(e) {a^{x}ba^{y}ba^{z} : x · y = z} 15. Dowiedź, że nast_{}epuj _{}ace j_{}ezyki nie s _{}a bezkontekstowe:

(a) {a^{i}b^{j}a^{k} : j = max {i, k}

(b) {a^{i}b^{i}c^{k} : k ≠ i}.

16. Sformuluj uvwxy-lemat o pompowaniu dla j_{}ezyków liniowych w którym |uvxy| = O(1).

Dowiedź, że j_{}ezyk {a^{i}b^{i}c^{j}d^{j} : i, j ∈ N} nie jest liniowy.

17. Dowiedź, że L = {x ∈ (a + b)^{∗}, #_{a}(x) = #_{b}(x)} nie jest liniowym j_{}ezykiem bezkontekstowym.

18. Udowodnij, że zbiór słów w nad alfabetem {a, b} maj _{}acych t_{}e sam _{}a liczb_{}e liter a co b nie jest liniowym j_{}ezykiem bezkontekstowym.

1.3 Automaty ze stosem

1. Skonstruować automaty ze stosem rozpoznaj _{}ace poznane wcześniej j_{}ezyki bezkontekstowe: zbiór palindromów, zbiór poprawnie uformowanych ci _{}agów nawiasów, zbiór słów, które maj _{}a dwa razy wi_{}ecej b niż a, zbiór ci _{}agów, które nie s _{}a postaci ww.

2. Dla liczby naturalnej n, niech bin(n) ∈ {0, 1}^{∗} b_{}edzie binarnym przedstawieniem liczby n. Skonstruować automat ze stosem rozpoznaj _{}acy j_{}ezyk

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

3. 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′).

4. 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).

5. 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′, Y Z

lub

q, a, Z →_{A′′} q′, ϵ

Czy dla takich automatów można nadal ograniczyć liczb_{}e stanów?

6. Maj _{}ac dany automat ze stosem akceptuj _{}acy j_{}ezyk L, skonstruować automaty ze stosem akceptuj _{}ace nast_{}epuj _{}ace j_{}ezyki:

• Prefix(L) = {w : (∃v)wv ∈ L}

• Suffix(L) = {w : (∃u)uw ∈ L}

• Subword(L) = {w : (∃u, v)uwv ∈ L}

• L^{R} = {w^{R} : w ∈ L}

• (*) Cycle(L) = {vw : wv ∈ L}

7. Maj _{}ac dany automat ze stosem akceptuj _{}acy j_{}ezyk L i automat skończony akceptuj _{}acy j_{}ezyk R, skonstruować automaty ze stosem akceptuj _{}ace nast_{}epuj _{}ace j_{}ezyki:

• LR^{−1}

• R^{−1}L

• L ∩ R

8. Dla danych j_{}ezykow regularnych L i M, skonstruować automat ze stosem rozpoznaj _{}acy j_{}ezyk ⋃_{i∈N}(L^{i} ∩ M^{i}). Uwaga: ten zbiór nie musi być regularny.

9. 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 _{}ace (przez pusty stos) o długości ≤ C|w|. Wskazówka: oszacować wysokość stosu w obliczeniu akceptuj _{}acym.

10. Niech A b_{}edzie automatem ze stosem. Dowieść, że zbiór słów, które s _{}a możliwymi zawartościami stosu automatu A, jest j_{}ezykiem regularnym. Formalnie, mamy na myśli zbiór

{α ∈ Γ^{∗} : (∃w, v ∈ Σ^{∗})(∃q ∈ Q) q_{I}, w, Z_{I} ⊢_{A} q, v, α}

Wywnioskować st _{}ad, że zbiór słów, które s _{}a możliwymi zawartościami stosu automatu A w jakimś obliczeniu akceptuj _{}acym, jest j_{}ezykiem bezkontekstowym.

11. Automat ze stosem A = (Σ, Γ, Q, q_{I}, Z_{I}, δ, F) nazywamy deterministycznym, jeśli w każdej sytuacji możliwy jest co najwyżej jeden ruch. Dokładniej:

• jeśli, dla pewnej pary q, Z, zachodzi q, ϵ, Z →_{A} p, α przy pewnych p, α, to dla żadnego σ ∈ Σ, nie zachodzi q, σ, Z →_{A} p′, α′, dla żadnych p′, α′;

• dla każdych q, σ, Z, istnieje co najwyżej jedna para p, α, taka że q, σ, Z →_{A} p, α.

J_{}ezyk bezkontekstowy jest deterministyczny jeśli jest rozpoznawany przez pewien deterministyczny automat ze stosem (w sensie stanów akceptuj _{}acych, tzn. L = L(A)). Dowieść, że j_{}ezyk {a^{n}b^{n} : n ∈ N} ∪ {a^{n}b^{2n} : n ∈ N} nie jest deterministycznym j_{}ezykiem bezkontekstowym.

12. Wykazać, że zbiór palindromów nad alfabetem dwuelementowym nie jest deterministycznym j_{}ezykiem bezkontekstowym.

1.4 Własności j_{}ezyków bezkontekstowych

1. Podaj przykład j_{}ezyka bezkontekstowego L t.że j_{}ezyk L = {x : (∃y) |x| = |y| ∧ xy ∈ L} nie jest bezkontekstowy.

2. Udowodnić, że przeci_{}ecie j_{}ezyka (deterministycznego) bezkontekstowego z regularnym jest też j_{}ezykiem (deterministycznym) bezkontekstowym.

3. Przeplotem słów w i v nazwiemy dowolne słowo długości |w|+|v|, które można rozbić na rozł _{}aczne podci _{}agi w i v. L i M jest zbiór wszystkich możliwych przeplotów słów w ∈ L, v ∈ M. J_{}ezyk ten oznaczamy L ∥ M. Udowodnij, ze przeplot j_{}ezyka bezkontekstowego i regularnego jest j_{}ezykiem bezkontekstowym. Podaj przykład j_{}ezyków bezkontekstowych L i M, dla których L ∥ M nie jest j_{}ezykiem bezkontekstowym.

4. Domkni_{}ecie przeplotne j_{}ezyka L określamy przez L^{♯} = L ∪ (L ∥ L) ∪ (L ∥ L ∥ L) ∪ . . .. Wykazać, że operacja domkni_{}ecia przeplotnego j_{}ezyka skończonego może dać w wyniku j_{}ezyk który nie jest bezkontekstowy.

5. Udowodnić, że jeśli X, Y s _{}a j_{}ezykami regularnymi to j_{}ezyk

L = ∑_{n≥1} X^{n} ∩ Y^{n}

jest bezkontekstowy.

6. Podać przykład j_{}ezyków regularnych X, Y t.że

∑_{n≥1}(X^{n} ∩ Y^{n}) = {a^{n}b^{n} : n ≥ 1}

7. Podaj j_{}ezyki regularne X, Y, Z t.że j_{}ezyk

∑_{n≥1}(X^{n} ∩ Y^{n} ∩ Z^{n})

nie jest bezkontekstowy.

8. Wskaż j_{}ezyk bezkontekstowy L, dla którego \sqrt{L} = \{w : ww ∈ L\} nie jest j_{}ezykiem bezkontekstowym.

9. Podaj przykład j_{}ezyka bezkontekstowego takiego. że {x : x^{k} ∈ L dla pewnego k} nie jest bezkontekstowy.

10. Rozważmy nast_{}epuj _{}acy morfizm:

h(a) = a, h(b) = b, h(a′) = a, h(b′) = b

oraz h(x) = ϵ dla symboli x ∈ {a, b, a′, b′} dla których morfizm nie został zdefiniowany powyżej. Wykazać, że j_{}ezyk EQ(h, g) = {w : h(w) = g(w)} nie jest bezkontekstowy.

11. Udowodnij, że jeśli U jest regularny to nast_{}epuj _{}acy j_{}ezyk jest bezkontekstowy {xy^{R} : x ≠ y, xy ∈ U}

12. J_{}ezyk ma własność prefiksow _{}a, gdy dla każdych dwóch słow z tego j_{}ezyka jedno z nich jest prefiksem drugiego. Wykaż, że jeśli j_{}ezyk bezkontekstowy ma własność prefiksow _{}a to jest on regularny.

13. Niech L ⊆ {a, b}^{∗} b_{}edzie j_{}ezykiem regularnym oraz h, g b_{}ed _{}a morfizmami. Udo-

wodnić, że nast_{}epuj _{}acy j_{}ezyk jest liniowym j_{}ezykiem bezkontekstowym {h(u)c(g(u))^{R} : u ∈ L}

14. Udowodnij, że przeci_{}ecie liniowego j_{}ezyka bezkontekstowego z regularnym jest j_{}ezykiem liniowym.

15. Dla j_{}ezyka L określamy Min(L) jako zbiór słów w L minimalnych ze wzgl_{}edu na porz _{}adek bycia prefiksem. (Zatem u ∈ Min(L) ⇔ nie istniej _{}a v ∈ L oraz w ≠ ϵ takie, że vw ∈ L.) Udowodnij, że dla deterministycznego j_{}ezyka bezkontekstowego L j_{}ezyk Min(L) jest również deterministycznym j_{}ezykiem bezkontekstowym.

16. Niech L = {a^{i}b^{j}c^{k} : k ≥ i lub k ≥ j}. Pokaż, że Min(L) nie jest j_{}ezykiem bezkontekstowym.

17. Zbiór Max(L) określamy analogicznie jak zbiór Min(L) w zadaniu 15. Podaj przykład j_{}ezyka bezkontekstowego L, dla którego Max(L) nie jest j_{}ezykiem bezkontekstowym.

18. Niech h_{1}, h_{2} b_{}ed _{}a morfizmami takimi, że alfabet wyjściowy nie zawiera $. Wykaż, że j_{}ezyki {x$y^{R} : h_{1}(x) = h_{2}(x)} i {x$y^{R} : h_{1}(x) ≠ h_{2}(x)} s _{}a liniowymi j_{}ezykami bezkontekstowymi.

19. Podzbiór M ⊆ N^{k} nazywamy liniowym jeśli można go przedstawić M = {a⃗ + n · b⃗ : n ∈ N}, dla pewnych wektorów a⃗, b⃗ ∈ N^{k}, a semi-liniowym, jeśli jest sum _{}a skończenie wielu zbiorów semi-lniowych.

(a) Udowodnij, że zbiór długości słów j_{}ezyka bezkontekstowego jest semi-liniowy.

(b) (*) Udowodnij twierdzenie Parikha głosz _{}ace, że dla j_{}ezyka bezkontekstowego L ⊆ Σ^{∗} zbiór (⊆ N^{|Σ|}) wektorów liczby wyst _{}apień liter z Σ w słowach z L jest semiliniowy.