J_{}ezyki, Automaty i Obliczenia

Zadania

Damian Niwiński i Wojciech Rytter

Październik 1998

1 Słowa i liczby

Do tej partii zadań może podejść Czytelnik bez żadnej znajomości teorii automatów.

1. Słowa pierwotne. Słowo w ∈ Σ^{∗} nazywamy pierwotnym (ang. primitive), jeśli nie da si_{}e go przedstawić w = v^{n}, inaczej niż dla n = 1 i v = w.

(a) Dowieść, że dla każdego słowa niepustego w, istnieje dokładnie jedno słowo pierwotne v, takie że w = v^{n}, dla pewnego n ≥ 1. Liczb_{}e n nazywamy wykładnikiem słowa w.

(b) O słowach wv i vw mówimy, że s _{}a w relacji koniugacji. Dowieść, że jest to relacja równoważności. Dowieść, że dwa słowa b_{}ed _{}ace w relacji koniugacji maj _{}a ten sam wykładnik. Jaka jest moc klasy abstrakcji relacji koniugacji dla słowa o długości m i wykładniku n?

2. J_{}ezyk nawiasowy. Wykazać, że zbiór poprawnie uformowanych ci _{}agów nawiasów może być zdefiniowany na dwa równoważne sposoby:

• Jako najmniejszy zbiór L zawieraj _{}acy ci _{}ag pusty oraz taki, że jeśli w, v ∈ L, to również (w), wv ∈ L.

• Zbiór słów nad alfabetem {(,)}, w których ilość “)” jest taka sama jak ilość “(”, a w każdym prefiksie ilość “)” jest niewi_{}eksza niż ilość “(” .

3. Zbiory semi–liniowe. Zbiór liczb naturalnych postaci {a + bn : n ∈ N}, dla ustalonych a, b ∈ N nazywamy liniowym. Zbiór bed _{}acy sum _{}a skończonej liczby zbiorów liniowych nazywamy semiliniowym. (Gdy sumowana rodzina jest pusta, otrzymujemy zbiór pusty.)

(a) Dowieść, że każdy zbiór postaci {a + b_{1}n_{1} + … + b_{k}n_{k} : n_{1}, …, n_{k} ∈ N}, dla ustalonych k i a, b_{1}, …, b_{k} ∈ N, jest semi–liniowy. Wskazówka. Wykorzystać podziały zbioru liczb naturalnych na klasy abstrakcji relacji przystawania modulo m, dla odpowiednio dobranych liczb m.

(b) W grafie zorientowanym ustalamy dwa wierzchołki. Interesuje nas zbiór długości wszystkich możliwych ścieżek pomi_{}edzy tymi wierzchołkami. Dowieść, że jest to zbiór semi–liniowy.

(c) Dowieść, że rodzina zbiorów semi–liniowych jest zamkni_{}eta na skończone sumy, przeci_{}ecia oraz na uzupełnienie wzgl_{}edem N.

4. Kody. Zbiór C ⊆ Σ^{+} nazywamy kodem jełi każde słowo w ∈ Σ^{∗} dopuszcza co najwyżej jedn _{}a faktoryzacj_{}e wzgl_{}edem C (tzn., da si_{}e “odkodować”).

Niech Σ = {a, b}. Dowieść, że zbiór {aa, baa, ba} jest kodem, a zbiór {a, ab, ba} nie jest.

2 J_{}ezyki regularne

2.1 Automaty skończone i wyrażenia regularne

1. Dowieść, że dla dowolnych j_{}ezyków L, M, (L^{∗}M^{∗})^{∗} = (L ∪ M)^{∗}.

2. Dodawanie. Rozważamy słowa nad alfabetem {0, 1}^{3}. Powiemy, że słowo ⟨a_{1}, b_{1}, c_{1}⟩ … ⟨a_{n}, b_{n}, c_{n}⟩ długości n reprezentuje dodawanie, jeśli liczba reprezentowana binarnie przez słowo c_{1} … c_{n} jest sum _{}a liczb reprezentowanych przez a_{1} … a_{n} i b_{1} … b_{n}. Na przykład, ci _{}ag ⟨0, 0, 1⟩⟨1, 1, 1⟩⟨0, 1, 0⟩⟨1, 1, 0⟩ reprezentuje dodawanie (5+7=12). Podać wyrażenie regularne opisuj _{}ace zbiór wszystkich słów reprezentuj _{}acych dodawanie.

3. Podzielność.

(a) Skonstruować skończony automat deterministyczny nad alfabetem {0, 1, …, 8, 9} rozpoznaj _{}acy zbiór dziesi_{}etnych reprezentacji wielokrotności liczby 7.

(b) Jak wyżej, ale przy reprezentacji odwrotnej, tj. poczynaj _{}ac od cyfr najmniej znacz _{}acych.

(c) Uogólnić niniejsze zadanie.

4. Alfabet jednoliterowy.

(a) Dowieść, że j_{}ezyk L ⊆ {a}^{∗} jest regularny wtedy i tylko wtedy, gdy zbiór liczb naturalnych {n : a^{n} ∈ L} jest semi–liniowy w sensie rozdziału 1.

(b) Dowieść, że dla dowolnego zbioru X ⊆ {a}^{∗}, j_{}ezyk X^{∗} jest regularny.

5. Zbiory semi–liniowe. Dowieść, że jeśli M ⊆ N jest zbiorem semi–liniowym, to j_{}ezyk {bin(m) : m ∈ M} jest regularny, gdzie bin(m) oznacza binarn _{}a reprezentacj_{}e liczby m.

Uwaga. Analogiczny fakt można udowodnić dla dowolnej reprezentacji, a zatem zbiór semi–liniowy jest regularny w reprezentacji o podstawie k, dla k ≥ 1. W przeciwnym kierunku wiadomo, że jeśli zbiór jest regularny w reprezentacjach o wzgl_{}ednie pierwszych podstawach p i q, to jest semi–liniowy (wniosek z Twierdzenia Cobhama).

6. Dowieść, że dla danych liczb a, b, p, r ∈ N, j_{}ezyk

L = {x$y : (a · bin(x) + b · bin(y)) ≡ r (mod p)}

jest regularny.

7. Dla danego automatu A rozpoznaj _{}acego j_{}ezyk L, skonstruować automat rozpo-

znaj _{}acy j_{}ezyk

Cycle(L) = {vu : uv ∈ L}

2.2 Własności j_{}ezyków regularnych

1. Niech L bedzie j_{}ezykiem regularnym nad alfabetem {0, 1}. Dowieść, że nast_{}epuj _{}acy j_{}ezyk jest regularny:

{w : w ∈ L∧ spośród słów o dlugości |w|, w jest najmniejsze w porz _{}adku leksykograficznym}

2. (*) Przyjmujemy, że każde niepuste słowo binarne w ∈ {0, 1}^{∗}, w = w_{1} … w_{k}, reprezentuje pewien ułamek w przedziale [0, 1),

bin(w) = w_{1} \frac{1}{2} + w_{2} \frac{1}{2^{2}} + … + w_{k} \frac{1}{2^{k}}

Dla liczby rzeczywistej r ∈ [0, 1], niech

L_{r} = {w : bin(w) ≤ r}

Dowieść, że j_{}ezyk L_{r} jest regularny wtedy i tylko wtedy, gdy liczba r jest wymierna.

3. Niech L b_{}edzie j_{}ezykiem regularnym. Dowieść, że nast_{}epuj _{}ace j_{}ezyki s _{}a również regularne:

• \frac{1}{2}L =_{df} \{w : (∃u) |u| = |w| ∧ wu ∈ L\}

• \sqrt{L} =_{df} \{w : ww ∈ L\}

4. (*) Niech L b_{}edzie j_{}ezykiem regularnym. Dowieść, że nast_{}epuj _{}ace j_{}ezyki s _{}a również regularne:

(a) Root(L) = {w : (∃n ∈ N) w^{n} ∈ L}

(b) Sqrt(L) = {w : (∃u)|u| = |w|^{2} ∧ wu ∈ L} Wskazówka. n^{2} = 1 + 3 + … (2n − 1).

(c) Log(L) = {w : (∃u)|u| = 2^{|w|} ∧ wu ∈ L} Wskazówka. 2^{n} = 1 + 2 + 2^{2} + 2^{n−1} + 1.

(d) 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}

5. Dowieść, że dla dowolnego j_{}ezyka regularnego L, j_{}ezyk

{w : w^{|w|} ∈ L}

jest również regularny.

6. Niech b_{}edzie dany j_{}ezyk regularny L i dowolne, niekoniecznie regularne, j_{}ezyki L_{1}, …, L_{m}. Skonstruować skończony automat deterministyczny rozpoznaj _{}acy j_{}ezyk nad alfabetem {1, …, m}

L = {i_{1}i_{2} … i_{k} : L_{i_{1}}L_{i_{2}} … L_{i_{k}} ⊆ L}

7. Dowieść, że zbiór palindromów nad alfabetem o co najmniej dwóch elementach nie jest regularny.

8. Niech Pal _{Σ}^{>1} oznacza zbiór palindromów o długości co najmniej 2 nad alfabetem Σ. Dowieść, że j_{}ezyk (Pal _{Σ}^{>1})^{∗} jest regularny wtedy i tylko wtedy, gdy |Σ| ≤ 2.

9. Dowieść, że zbiór wyrażeń regularnych nie jest regularny.

10. Dowieść, że nast_{}epuj _{}ace j_{}ezyki nie s _{}a regularne:

• {a^{2^{n}} : n ∈ N}

• {a^{p} : p jest liczb _{}a pierwsz _{}a}

• {a^{i}b^{j} : nwd(i, j) = 1}

11. Niech L b_{}edzie j_{}ezykiem regularnym. Dowieść, że j_{}ezyki:

• L_{+−−} = {w : (∃u) |u| = 2|w| ∧ wu ∈ L}

• L_{++−} = {w : (∃u) 2|u| = |w| ∧ wu ∈ L}

• L_{−+−} = {w : (∃u, v) |u| = |v| = |w| ∧ uwv ∈ L} s _{}a j_{}ezykami regularnymi, a j_{}ezyk

• L_{+−+} = {uv : (∃w) |u| = |v| = |w| ∧ uwv ∈ L} może nie być regularny.

12. Czy z faktu, że j_{}ezyk Cycle(L) = {vu : uv ∈ L} jest regularny, można wnioskować, że j_{}ezyk L jest regularny?

13. 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. Na przykład, przeplotami słów ab i acb s _{}a słowa abacb, aabcb, acabb, acbab, aacbb. Przeplotem j_{}ezyków L i M jest zbiór wszystkich możliwych przeplotów słów w ∈ L, v ∈ M. J_{}ezyk ten oznaczamy L ∥ M. Dowieść, że jeśli L i M s _{}a j_{}ezykami regularnymi, to L ∥ M jest również regularny.

14. Określamy L^{♯} = L ∪ (L ∥ L) ∪ (L ∥ L ∥ L) ∪. . .. Podać przykład j_{}ezyka regularnego L nad dwuelementowym alfabetem, dla którego L^{♯} nie jest j_{}ezykiem regularnym.

15. Dowieść, że jeśli w Zadaniu 2 z punktu 2.1 zamienimy dodawanie przez mnożenie, to otrzymany j_{}ezyk (nad alfabetem {0, 1}^{3}) jest wprawdzie dobrze określony, ale nie jest regularny.

16. Zaprojektować algorytm, który dla danych automatów deterministycznych A, B, rozstrzyga, czy L(A) = L(B).

17. Niech A b_{}edzie ustalonym automatem deterministycznym. Zaprojektować algorytm, który dla danej liczby n oblicza ilość słów długości n akceptowanych przez A.

2.3 Automaty minimalne.

1. Niech w ∈ Σ^{∗} b_{}edzie słowem o długości |w| = n > 0. Dowieść, że minimalny automat deterministyczny rozpoznaj _{}acy wszystkie słowa nad Σ, które zawieraj _{}a w jako podsłowo, ma dokładnie n + 1 stanów.

2. Niech w ∈ Σ^{∗} b_{}edzie słowem o długości |w| = n > 0. Dowieść, że minimalny automat deterministyczny rozpoznaj _{}acy wszystkie podsłowa słowa w ma nie wi_{}ecej niż 2n stanów.

3. Trzy drużyny piłkarskie A, B i C rozgrywaj _{}a mi_{}edzy sob _{}a seri_{}e spotkań towarzyskich, przy czym umówiły si_{}e, że każdy kolejny mecz jest rozgrywany pomi_{}edzy drużyn _{}a, która wygrała poprzedni mecz i drużyn_{}e, która nie brała udziału w tym spotkaniu (tzn. jeśli drużyna X wygrała z drużyn _{}a Y, to nast_{}epny mecz rozegraj _{}a X i Z). Zakładaj _{}ac, że nie ma remisów, rozważamy zbiór słów nad alfabetem {A, B, C}, stanowi _{}acych ci _{}agi możliwych wyników spotkań. Dowieść, że jest to j_{}ezyk regularny. Zbudować minimalny automat deterministyczny, który go rozpoznaje.

4. Pan X zakupił pakiety trzech różnych akcji: A, B i C. Każdego dnia bada wzajemne położenie wartości swoich akcji, które może być reprezentowane jako uporz _{}adkowanie zbioru {A, B, C}, w kierunku od najmniej do najbardziej wartościowej. (Przyjmujemy założenie, że dwie różne akcje maj _{}a zawsze różne wartości.) Pan X postanowił, że jeśli w ci _{}agu dwóch kolejnych dni któraś z akcji dwukrotnie spadnie na niższ _{}a pozycj_{}e, to sprzeda t_{}e akcj_{}e. Np. jeśli kolejne notowania (w tym wypadku: uporz _{}adkowania) s _{}a (A, B, C), (B, C, A), (C, B, A) to pan X sprzeda pakiet akcji C. Rozważamy zbiór G wszystkich uporz _{}adkowań liniowych zbioru {A, B, C}. Dowieść, że zbiór tych ci _{}agów nad alfabetem G, które opisuj _{}a takie wyniki notowań giełdowych, przy których pan X nie pozb_{}edzie si_{}e żadnego pakietu akcji, jest j_{}ezykiem regularnym. Znaleźć liczb_{}e stanów automatu minimalnego akceptuj _{}acego ten j_{}ezyk.

5. Pan X postanowił, że każdego dnia b_{}edzie pracował lub nie, przestrzegaj _{}ac przy tym zasady, by na żadne siedem kolejnych dni nie przypadało wi_{}ecej niż cztery dni pracy. Możliwy rozkład dni pracy pana X w ci _{}agu n kolejnych dni możemy przedstawić jako n-bitowe słowo, gdzie 1 odpowiada dniowi pracy, a 0 dniowi odpoczynku. Dowieść, że zbiór wszystkich tak otrzymanych słów jest j_{}ezykiem regularnym (nad alfabetem {0, 1}). Znaleźć minimalny automat deterministyczny.

6. Eksplozja stanów. Niech Σ = {0, 1, …, k} i niech dla m = 1, …, k, L_{m} b_{}edzie zbiorem słów v nad Σ o nast_{}epuj _{}acej własności:

m wyst_{}epuje w v, ale przed pierwszym i pomi_{}edzy kaźdymi dwoma kolejnymi wyst _{}apieniami m, m − 1 wyst_{}epuje co najmniej dwa razy.

Nietrudno jest skonstruować deterministyczny automat o 4 stanach rozpoznaj _{}acy L_{m}.

Dowieść, że każdy (nawet niedeterministyczny) automat rozpoznaj _{}acy j_{}ezyk L_{1} ∩ … ∩ L_{k} musi mieć co najmniej 2^{k+1} − 1 stanów.

Wskazówka. Oszacować od dołu długość najkrótszego słowa w tym j_{}ezyku.