Jȩzyki, Automaty i Obliczenia. Odcinek 1

Jȩzyki regularne i automaty skończone

Damian Niwiński

Październik 2003

1 Podstawowe operacje na j_{}ezykach

Rozważamy skończony zbiór Σ, który nazywamy alfabetem, a jego elementy symbolami. Skończony ci _{}ag symboli nazywamy słowem, w szczególności ci _{}ag pusty jest słowem pustym oznaczanym ϵ. Zbiór wszystkich słów nad alfabetem Σ oznaczamy Σ^{∗}. Słowo w ∈ Σ^{∗} można przedstawić w = (w_{1}, …, w_{n}) gdzie w_{i} ∈ Σ, dla i = 1, …, n. Liczba n ≥ 0 jest długości _{}a słowa w oznaczan _{}a |w|, zauważmy, że |ϵ| = 0. Dla dwóch słów w = (w_{1}, …, w_{n}) i v = (v_{1}, …, v_{m}), konkatenacj _{}a w i v jest słowo

wv = (w_{1}, …, w_{n}, v_{1}, …, v_{m})

Łatwo sprawdzić, że operacja konkatenacji jest ł _{}aczna, tzn. (wv)u = w(vu), co uzasadnia notacj_{}e beznawiasow _{}a wvu. Utożsamiaj _{}ac słowa jednoliterowe z literami, mamy w szczególności w = w_{1} … w_{n}. Zauważmy, że słowo puste jest elementem neutralnym operacji konkatenacji, tzn. wϵ = ϵw = w.

Uwaga. W j_{}ezyku algebry mówimy, że zbiór Σ^{∗} z operacj _{}a konkatenacji i słowem pustym tworzy struktur_{}e zwan _{}a monoidem.

Dla każdego przedstawienia u = wv, słowo w jest prefiksem (segmentem pocz _{}atkowym) a słowo v sufiksem słowa u. Relacja “być prefiksem” jest relacj _{}a cz_{}eściowego porz _{}adku, któr _{}a b_{}edziemy oznaczać po prostu ≤. Oczywiście, słowo puste jest elementem najmniejszym w tej relacji.

Zbiory słów nazywamy j_{}ezykami. Oprócz zwykłych operacji teoriomnogościowych: sumy, przeci_{}ecia i różnicy, b_{}edziemy wykonywać nad j_{}ezykami pewne operacje specjalne.

Konkatenacj _{}a j_{}ezyków L, M ⊆ Σ^{∗} jest j_{}ezyk

LM = {wv : w ∈ L, v ∈ M}

Nietrudno zauważyć, że konkatenacja j_{}ezyków jest ł _{}aczna.

Pytanie. Co jest elementem neutralnym operacji konkatenacji j_{}ezyków?

W notacji zwykle zakłada si_{}e, że operacja konkatenacji wi _{}aże silniej niż operacje teoriomnogościowej sumy i przeci_{}ecia, np. AB ∪C znaczy tyle samo co (AB)∪C. Zauważmy, że konkatenacja jest rozdzielna wzgl_{}edem operacji sumy, tzn. dla dowolnych j_{}ezyków K, L, M,

K(L ∪ M) = KL ∪ KM
(K ∪ L)M = KM ∪ LM

Pytanie. Czy operacja konkatenacji jest rozdzielna wzgl_{}edem operacji cz_{}eści wspólnej ∩?

Prawo rozdzielności można uogólnić na przypadek, kiedy sumowanie obejmuje dowoln _{}a rodzin_{}e j_{}ezyków.

Fakt 1 Niech L ⊆ P (Σ^{∗}) b_{}edzie rodzin _{}a j_{}ezyków i niech M ⊆ Σ^{∗}. Wówczas

M ⋃ L = ⋃_{K∈L} MK

(⋃ L)M = ⋃_{K∈L} KM

□

Z kolei określimy operacj_{}e iteracji zwan _{}a też operacj _{}a “gwiazdki”

L^{∗} = ⋃_{n<ω} L^{n}

gdzie L^{0} = {ϵ} i L^{n+1} = L^{n}L. (Symbol ω oznacza pierwsz _{}a nieskończon _{}a liczb_{}e porz _{}adkow _{}a, czyli innymi słowy zbiór liczb naturalnych.) Ćwiczenie. (a) Czemu jest równe ∅^{∗}?

(b) Wykazać, że dla dowolnego L ⊆ Σ^{∗}, (L^{∗})^{∗} = L^{∗}.

O ile nie b_{}edzie to prowadziło do nieporozumień, b_{}edziemy opuszczać akolady {} dla zbiorów jednoelementowych, pisz _{}ac np. abLbaa zamiast {ab}L{ba}{a}.

Przykład 1 Niech Σ = {a, b}. Zbiór {aa}^{∗} obejmuje słowa złożone z parzystej ilości a, Σ^{∗}aΣ^{∗} jest zbiorem słów zawieraj _{}acych przynajmniej jedno a, natomiast (Σ−{a})^{∗}(a(Σ− {a})^{∗}a(Σ − {a})^{∗})^{∗} zbiorem słów, w których liczba wyst _{}apień a jest parzysta.

Rodzina j_{}ezyków nad ustalonym alfabetem wraz z operacjami teorio-mnogościowymi oraz operacjami konkatenacji i gwiazdki tworzy pewn _{}a struktur_{}e algebraiczn _{}a. Jak to cz_{}esto bywa w matematyce, struktura algebraiczna zach_{}eca do budowania i rozwi _{}azywania równań. Udowodnimy teraz pewn _{}a własność równań, jaka b_{}edzie przydatna później.

Lemat 1 (Arden) Niech A, B ⊆ Σ^{∗}, ϵ ∉ A. Wówczas równanie

X = AX ∪ B

ma dokładnie jedno rozwi _{}azanie w P(Σ^{∗}) równe A^{∗}B.

Dowód. Nietrudno sprawdzić, że A^{∗}B = AA^{∗}B ∪ B, zatem X = A^{∗}B jest rozwi _{}azaniem równania. Z kolei przypuśćmy, że jakiś j_{}ezyk M spełnia M = AM ∪ B, pokażemy, że M = A^{∗}B.

“⊆” Przez indukcj_{}e ze wzgl_{}edu na |w|, pokażemy, że w ∈ M ⇒ w ∈ A^{∗}B. Gdy w = ϵ, to ponieważ ϵ ∉ A i w ∈ AM ∪ B, wiec w ∈ B ⊆ A^{∗}B. Gdy |w| > 0, to albo w ∈ B, albo w = vu, gdzie v ∈ A i u ∈ M, przy czym |u| < |w|, zatem, z założenia indukcyjnego, u ∈ A^{∗}B. W obu przypadkach w ∈ A^{∗}B.

“⊇” Z rozdzielności konkatenacji wzgl_{}edem dowolnej sumy, mamy w szczególności A^{∗}B = ⋃_{n<ω}(A^{n}B). Z faktu, że M spełnia równanie wynika natychmiast, że B = A^{0}B ⊆ M, oraz że A^{n}B ⊆ M implikuje A(A^{n}B) = A^{n+1}B ⊆ M, co kończy dowód. □

Z kolei rozważymy operacje lewo- i prawostronnych ilorazów.

L^{−1}M = {w : ∃v ∈ L vw ∈ M}
LM^{−1} = {v : ∃w ∈ M vw ∈ L}

Uwaga. T_{}e notacj_{}e trzeba rozumieć całościowo, samo wyrażenie L^{−1} nie oznacza żadnego j_{}ezyka.

Przykład 2 Zbiór słów j_{}ezyka L, które zaczynaj _{}a si_{}e od a można przedstawić a(a^{−1}L).

Wprowadzimy teraz bardzo ważn _{}a w studiach nad j_{}ezykami operacj_{}e podstawienia. Niech Σ, Γ b_{}ed _{}a alfabetami i niech f : Σ → P (Γ^{∗}) b_{}edzie funkcj _{}a przyporz _{}adkowuj _{}ac _{}a literom z Σ j_{}ezyki nad Γ. Funkcj_{}e f rozszerzamy do funkcji f̂: Σ^{∗} → P (Γ^{∗}) przez

f̂(ϵ) = {ϵ}
f̂(wσ) = f̂(w)f(σ)

dla w ∈ Σ^{∗}, σ ∈ Σ. Wreszcie, funkcj_{}e f̂ rozszerzamy do operacji określanej na j_{}ezykach (oznaczanej tak samo). Mianowicie, dla L ⊆ Σ^{∗}, kładziemy

f̂(L) = ⋃_{w∈L} f̂(w)

Funkcj_{}e f̂ nazywamy podstawieniem indukowanym przez f. Jeżeli, dla każdego σ ∈ Σ, moc zbioru f(σ), |f(σ)| = 1, podstawienie nazywamy homomorfizmem.

Uwaga. Gdy Γ = Σ = {σ_{1}, …, σ_{n}}, podstawienie można uważac za n + 1 argumentow _{}a operacj_{}e na P (Σ^{∗}), która j_{}ezykom L, M_{1}, …, M_{n}, przyporz _{}adkowuje rezultat podstawienia indukowanego przez σ_{i} ↦ M_{i}, zastosowanego do L.

Przykład 3 Podstawienie indukowane przez a ↦ ϵ powoduje “wymazanie” litery a. Podstawienie indukowane przez x ↦ {1, 2, ϵ}, zastosowane do słowa yx+zx, daje w rezultacie zbiór

{y1 + z1, y1 + z2, y1 + z, y2 + z1, y2 + z2, y2 + z, y + z1, y + z2, y + z}

Ćwiczenia

1. Przedstawić j_{}ezyk {ab}^{∗} jako kombinacj_{}e j_{}ezyków W = {a, b}^{∗}, {a}, {b}, używaj _{}ac operacji konkatenacji, sumy i różnicy, ale nie używaj _{}ac ∗.

Uwaga : dla j_{}ezyka {aa}^{∗} jest to niemożliwe.

2. Podać przykład, że L(K ∩ M) ≠ LK ∩ LM.

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

4. Jakie relacje zachodz _{}a pomi_{}edzy zbiorami L^{∗}, L^{−1}L^{∗} i L^{∗}L^{−1}?

5. Czy z faktu, że LK = M wynika, że L^{−1}M = K ?

6. Czy (LK^{−1})M = L(K^{−1}M) ?

7. Kody. Zbiór C ⊆ Σ^{+} nazywamy kodem jeśli 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 Wyrażenia regularne

Niech Reg(Σ) b_{}edzie najmniejsz _{}a rodzin _{}a j_{}ezyków nad alfabetem Σ, która zawiera zbiór ∅, dla każdej litery σ ∈ Σ zawiera zbiór {σ}, a ponadto, jeśli L i M s _{}a j_{}ezykami w Reg(Σ), to również LM, L ∪ M i L^{∗} należ _{}a do tej rodziny. Zbiory z rodziny Reg(Σ) nazywamy j_{}ezykami regularnymi nad Σ. Kiedy dopuszczamy dowolne alfabety, mówimy o klasie j_{}ezyków regularnych.

Tradycyjnie, j_{}ezyki regularne s _{}a reprezentowane poprzez tzw. wyrażenia regularne, podobnie jak np. liczby całkowite mog _{}a być reprezentowane przez wyrażenia arytmetyczne. Wyrażeniami takimi posługiwaliśmy si_{}e już nieformalnie przed chwil _{}a, a teraz zdefiniujemy je dokładnie. Z naszego punktu widzenia istotne jest to, że wyrażenia używane do reprezentacji j_{}ezyków, same s _{}a słowami nad pewnym alfabetem.

Zbiór wyrażeń regularnych nad alfabetem Σ, R(Σ), określamy jako najmniejszy zbiór słów nad alfabetem Σ ∪ {∅, +, ∗, (,)}, taki że

• ∅ ∈ R(Σ),

• dla każdego σ ∈ Σ, σ ∈ R(Σ),

• jełi r, s ∈ R(Σ), to (rs), (r + s), (r^{∗}) ∈ R(Σ)

Interpretacj _{}a wyrażenia r ∈ R(Σ) jest j_{}ezyk L[r] ⊆ Σ^{∗} określony indukcyjnie w łatwy do odgadni_{}ecia sposób: L[∅] = ∅, L[σ] = {σ}, L[(r + s)] = L[r] ∪ L[s] L[(rs)] = L[r] L[s], L[(r^{∗})] = L[r]^{∗}. Jak można oczekiwać, mamy nast_{}epuj _{}acy

Fakt 2 J_{}ezyk L ⊆ Σ^{∗} jest regularny wtedy i tylko wtedy, gdy L = L[r], dla pewnego wyrażenia regularnego r ∈ R(Σ).

Dowód. Łatwo jest widzieć, że klasa j_{}ezyków opisywanych przez wyrażenia regularne nad Σ (tzn. {L[r] : r ∈ R(Σ)})

(*) zawiera zbiory ∅ i {σ}, dla σ ∈ Σ, oraz jeśli L i M s _{}a w tej klasie, to należ _{}a tam również LM, L ∪ M i L^{∗}.

A zatem, skoro Reg(Σ) jest najmniejsz _{}a rodzin _{}a o własności (*), to każdy j_{}ezyk regularny jest postaci L[r], dla pewnego r ∈ R(Σ).

Na odwrót, jeśli klasa K spełnia warunek (*), to przez indukcj_{}e ze wzgl_{}edu na długość wyrażenia regularnego r, łatwo jest wykazać, że L[r] ∈ K. Stosuj _{}ac t_{}e uwag_{}e do K = Reg(Σ), otrzymujemy, że każdy j_{}ezyk L[r] jest regularny. □

Uwaga 1. W zastosowaniach praktycznych zbiór wyrażeń regularnych cz_{}esto określa si_{}e bardziej liberalnie, dopuszczaj _{}ac opuszczanie nawiasów. Przyjmuje si_{}e wówczas, że “*” wi _{}aże silniej niż “+” i konkatenacja, a konkatenacja silniej niż “+”. Np. ab^{∗} + c ma taki sam sens jak ((a(b^{∗})) + c).

Uwaga 2. Nietrudno zauważyć, że ten sam j_{}ezyk może być reprezentowany przez wiele wyrażeń regularnych. Np. L[(a^{∗})] = L[(aa)^{∗} + a(aa)^{∗}]. Prowadzi to do pytań o reprezentacje w jakimś sensie optymalne, pytań, które czasem okazuj _{}a si_{}e nieoczekiwanie trudne. Np. algorytm znajdowania wyrażenia o minimalnym zagnieżdżeniu operacji * został podany przez Hashigushi’ego dopiero w roku 1988, a dowód poprawności liczy kilkadzi_{}esi _{}at stron. (Dla porównania, omawiane w nast_{}epnych rozdziałach Twierdzenie Kleene’go o wyrażeniach regularnych pochodzi z r. 1956.)

Jak zobaczymy nieco później, klasa j_{}ezyków regularnych obejmuje wiele naturalnych przykładów j_{}ezyków, również o znaczeniu praktycznym. Z drugiej strony, klasa ta jest zamkni_{}eta na wiele operacji, jakie z danych j_{}ezyków tworz _{}a nowy j_{}ezyk. Wprost z definicji wynika, że suma, konkatenacja i gwiazdka j_{}ezyków regularnych jest j_{}ezykiem regularnym.

Pokażemy teraz, że również operacja podstawienia nie wyprowadza poza j_{}ezyki regularne.

Fakt 3 Niech f : Σ → P (Γ^{∗}) b_{}edzie funkcj _{}a tak _{}a, że, dla każdego σ ∈ Σ, f(σ) jest j_{}ezykiem regularnym. Wówczas, jeśli L ⊆ Σ^{∗} jest j_{}ezykiem regularnym, to f̂(L) jest również j_{}ezykiem regularnym.

Dowód. Z uwagi na indukcyjn _{}a definicj_{}e rodziny j_{}ezyków regularnych Reg(Σ), wystarczy wykazać, że rodzina j_{}ezyków regularnych L ⊆ Σ^{∗}, dla których f̂(L) jest również j_{}ezykiem regularnym, zawiera ∅ oraz zbiory {σ}, dla σ ∈ Σ i jest zamkni_{}eta na operacje binarnej sumy, konkatenacji i gwiazdki. Gdy L = ∅, lub L = {σ}, dla σ ∈ Σ, teza jest oczywista. Dalej, nietrudno jest sprawdzić, że

f̂(L_{1}L_{2}) = f̂(L_{1})f̂(L_{2})
f̂(L_{1} ∪ L_{2}) = f̂(L_{1}) ∪ f̂(L_{2})
f̂(L_{1}^{∗}) = f̂(L_{1})^{∗}

Zatem, gdy L_{1} i L_{2} s _{}a jezykami regularnymi spełniaj _{}acymi tez_{}e Faktu, to spełniaj _{}a j _{}a również L_{1}L_{2}, L_{1} ∪ L_{2} i L_{1}^{∗}. Ta uwaga kończy dowód. □

Ćwiczenia

1. Napisać wyrażenie regularne nad alfabetem {0, 1}, opisuj _{}ace nast_{}epuj _{}acy j_{}ezyk:

(a) zbiór słów zawieraj _{}acych dwa kolejne wyst _{}apienia tego samego symbolu,

(b) zbiór słów nie zawieraj _{}acych dwóch kolejnych wyst _{}apień tego samego symbolu,

(c) zbiór słów o długości nieparzystej,

(d) zbiór słów, gdzie po każdej parze kolejnych zer (niekoniecznie bezpośrednio po) wyst _{}api para kolejnych jedynek,

(e) zbiór słów nie zawieraj _{}acych 101 jako podsłowa,

2. Napisać wyrażenie regularne nad alfabetem {0, 1}, opisuj _{}ace nast_{}epuj _{}acy j_{}ezyk:

(a) zbiór słów zawieraj _{}acych parzyst _{}a liczb_{}e jedynek,

(b) zbiór słów przedstawiaj _{}acych w postaci binarnej liczby naturalne podzielne przez 3.

3. Opisać w j_{}ezyku polskim lub dowolnym j_{}ezyku naturalnym zbiory oznaczone przez wyrażenia regularne:

(a) (1 + 01 + 001)^{∗}(ϵ + 0 + 00)

(b) (11 + 0)^{∗} + ((11)^{∗}1 + 0)^{∗}

4. Skonstruować wyrażenie regularne nad alfabetem {0, 1}^{3}, opisuj _{}ace zbiór takich śłów (a_{1}, b_{1}, c_{1}), (a_{2}, b_{2}, c_{2}), …, (a_{k}, b_{k}, c_{k}), że a_{1}a_{2} … a_{k} + b_{1}b_{2} … b_{k} = c_{1}c_{2} … c_{k}, gdzie ci _{}agi a_{1}a_{2} … a_{k}, b_{1}b_{2} … b_{k}, c_{1}c_{2} … c_{k} traktuje si_{}e jako przedstawienia liczb naturalnych w postaci binarnej, ewentualnie poprzedzone zerami. (Jeśli trójki (a, b, c) zapisywać pionowo, to słowo takie przedstawia zwykłe dodawanie pisemne.)

5. Lustrzanym odbiciem słowa w = w_{1}w_{2} … w_{k} jest słowo

w^{R} =_{df} w_{k}w_{k−1} … w_{2}w_{1}

Dla j_{}ezyka L,

L^{R} =_{df} {w^{R} : w ∈ L}

Opisać algorytm, który, dla danego wyrażenia regularnego α konstruuje wyrażenie α^{R} o tej samej długości, takie, że L[α^{R}] = (L[α])^{R}.

6. (*) Dowieść, że dla dowolnego podzbioru L ⊆ {0}^{∗}, j_{}ezyk L^{∗} jest regularny.

2.2 Automaty skończone

Niedeterministyczny automat skończony (w dalszym ci _{}agu krótko: automat skończony) nad alfabetem Σ jest układem

A = (Σ, Q, I, δ, F)

gdzie • Q jest skończonym zbiorem stanów,

• I ⊆ Q jest zbiorem stanów pocz _{}atkowych,

• δ ⊆ Q × Σ × Q jest relacj _{}a przejścia,

• F ⊆ Q jest zbiorem stanów akceptuj _{}acych.

Elementy relacji δ b_{}edziemy nazywać przejściami (ang. transition), a fakt, że przejście (q, σ, q′) należy do δ b_{}edziemy także zapisywać q →^{σ} q′. Intuicyjnie, powyższe przejście rozumiemy nast_{}epuj _{}aco: jeśli automat znajduje si_{}e w stanie q, to po otrzymaniu informacji a (np. po przeczytaniu kodu litery a na taśmie) może zmienić stan na q′. Zauważmy, że stanów q′ o tej własności może być wiele, może też nie być żadnego takiego stanu; na tym właśnie polega niedeterminizm. Jeśli dla każdego stanu q i litery a, istnieje dokładnie jeden stan q′, taki że q →^{σ} q′, to automat nazywamy deterministycznym^{1}. Poj_{}eciem tym zajmiemy si_{}e jeszcze w dalszym ci _{}agu wykładu.

Relacj_{}e przejścia δ rozszerzymy do relacji δ̂ ⊆ Q×Σ^{∗} ×Q, określonej jako najmniejszy podzbiór Q × Σ^{∗} × Q, taki że

• (q, ϵ, q) ∈ δ̂, dla każdego q ∈ Q,

• jeśli (q, w, r) ∈ δ̂ i (r, σ, p) ∈ δ, to (q, wσ, p) ∈ δ̂.

Stwierdzenie, że (q, w, q′) ∈ δ̂, b_{}edziemy także zapisywać q →^{w} q′. (Jeśli w = σ jest słowem złożonym z jednej litery, to notacja ta pokrywa si_{}e z notacj _{}a wprowadzon _{}a wcześniej dla przejść, bo (q, σ, q′) ∈ δ̂ ⇔ (q, σ, q′) ∈ δ.)

Relacj_{}e δ̂ możemy scharakteryzować w sposób bardziej dynamiczny, odwołuj _{}ac si_{}e do możliwych ci _{}agów kolejnych przejść, jakie automat może wykonać, przyjmuj _{}ac informacj_{}e zawart _{}a w dostarczonym mu słowie. Dowód poniższej charakteryzacji można łatwo przeprowadzić przez indukcj_{}e ze wzgl_{}edu na długość słowa. Szczegóły pozostawiamy Czytelniczce lub Czytelnikowi.

Fakt 4 Niech q, q′ ∈ Q, w ∈ Σ^{∗}. Wówczas q →^{w} q′ wtedy i tylko wtedy, gdy w = ϵ i q = q′ lub w = σ_{1} … σ_{n}, gdzie n > 0 i σ_{i} ∈ Σ, dla i = 1, …, n, i istnieje ci _{}ag stanów q_{0}, q_{1}, …, q_{n}, taki że

q = q_{0} →^{σ_{1}} q_{1} →^{σ_{2}} q_{2} … q_{n−2} →^{σ_{n−1}} q_{n−1} →^{σ_{n}} q_{n} = q′

□

Ci _{}ag przejść w postaci o jakiej mowa w powyższym fakcie, tzn.

(q_{0}, σ_{1}, q_{1}), (q_{1}, σ_{2}, q_{2}), …, (q_{n−2}, σ_{n−1}, q_{n−1}), (q_{n−1}, σ_{n}, q_{n})

lub, w notacji “strzałkowej”

q_{0} →^{σ_{1}} q_{1} →^{σ_{2}} q_{2} … q_{n−2} →^{σ_{n−1}} q_{n−1} →^{σ_{n}} q_{n}

1W niektórych opracowaniach można spotkać słabsz _{}a definicj_{}e, w której dokładnie jeden jest zast _{}apione przez co najwyżej jeden. Automat deterministyczny w tym słabszym sensie łatwo jest sprowadzić do wymaganej przez nas postaci dokładaj _{}ac co najwyżej jeden stan (,,czarn _{}a dziur_{}e”).

nazwiemy przebiegiem automatu A, na słowie σ_{1}σ_{2} … σ_{n}, startuj _{}acym ze stanu q_{0} i zakończonym w stanie q_{n}.

Przebieg nazwiemy obliczeniem, gdy jego stan startowy należy do I. Obliczenie jest akceptuj _{}ace, gdy jego stan końcowy należy do F. Słowo w ∈ Σ^{∗} jest akceptowane (czasem mówi si_{}e także : rozpoznawane) przez automat A, jeśli istnieje obliczenie akceptuj _{}ace na słowie w (nie wykluczamy, że automat niedeterministyczny może mieć na słowie akceptowanym również obliczenia nie akceptuj _{}ace). Zauważmy, że słowo ϵ jest akceptowane wtedy i tylko wtedy, gdy I ∩ F ≠ ∅. Zbiór słów akceptowanych przez A stanowi j_{}ezyk akceptowany przez A, oznaczany L(A). Mamy wi_{}ec

L(A) = {w ∈ Σ^{∗} : q →^{w} q′ dla pewnych q ∈ I, q′ ∈ F }

Mówimy, że j_{}ezyk L ⊆ Σ^{∗} jest rozpoznawalny przez automat skończony (po angielsku: finite–state recognizable), jeśli L = L(A) dla pewnego automatu A.

Przykład 4 Rozważmy automat A = (Σ, Q, I, δ, F), gdzie Σ = {0, 1}, Q = {q_{0}, q_{1}}, I = {q_{0}}, δ = {(q_{0}, 0, q_{0}), (q_{0}, 1, q_{1}), (q_{1}, 0, q_{1}), (q_{1}, 1, q_{0})}, F = {q_{1}}.

Nietrudno wykazać, że L(A) jest zbiorem słów, które zawieraj _{}a nieparzyst _{}a liczb_{}e jedynek.

Przykład 5 Niech A = ({0, 1}, {q_{0}, q_{1}, q_{2}, q_{3}}, {q_{0}}, δ, {q_{0}}) b_{}edzie automatem, którego relacja (w tym przypadku funkcja) δ przedstawiona jest na rysunku.

L(A) jest zbiorem tych słów zero-jedynkowych, w których zarówno 0 jak i 1 wyst_{}epuj _{}a parzyst _{}a ilość razy.

Ćwiczenia

1. Skonstruować automat nad alfabetem {0, 1, …, 8, 9} rozpoznaj _{}acy

(a) zbiór słów reprezentuj _{}acych liczby podzielne przez 7,

(b) zbiór słów, których lustrzane odbicia s _{}a podzielne przez 7.

(c) Skonstruować automat deterministyczny rozpoznaj _{}acy zbiór z poprzedniego punktu.

(d) Uogólnić niniejsze zadanie.

2. Skonstruować automat niedeterministyczny rozpoznaj _{}acy zbiór słów nad alfabetem {a, b} o długości co najmniej 2, takich, że przedostatnim symbolem jest a. Skonstruować automat deterministyczny rozpoznaj _{}acy ten sam j_{}ezyk.

3. Narysować automat rozpoznaj _{}acy zbiór słów o nast_{}epuj _{}acej własności : pewne dwa a s _{}a rozdzielone słowem o długości 3k, dla pewnego k.

4. Dla danego automatu A, skonstruować automat rozpoznaj _{}acy j_{}ezyk (L(A))^{R}.

5. Dla danych automatów A i B, skonstruować automat rozpoznaj _{}acy j_{}ezyk L(A) ∩ L(B).

6. Dla danych automatów A i B, skonstruować automaty rozpoznaj _{}ace j_{}ezyki (L(A))^{−1}L(B) i L(A)(L(B))^{−1}.

7. Wykazać, że dla dowolnego automatu A nad alfabetem Σ i dowolnego j_{}ezyka X ⊆ Σ^{∗}, istniej _{}a automaty rozpoznaj _{}ace j_{}ezyki X^{−1}L(A) i L(A)X^{−1}.

Uwaga. Dowód istnienia odpowiednich automatów nie może być tutaj konstruktuwny, gdyż zbiór X nie jest zadany w sposób efektywny.

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

znaj _{}acy j_{}ezyk

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

2.3 Twierdzenie Kleene’go

Naszym celem b_{}edzie teraz wykazanie, że automaty skończone rozpoznaj _{}a dokładnie j_{}ezyki regularne. B_{}edzie to pierwszy w tym wykładzie rezultat pokazuj _{}acy równoważność dwóch modeli obliczeń: w tym wypadku wyrażeń regularnych i automatów skończonych. Podkreślmy, że, teraz i w przyszłości, interesować nas b_{}edzie nie tylko samo istnienie jakiegoś obiektu (np. wyrażenia regularnego opisuj _{}acego j_{}ezyk rozpoznawalny przez automat), ale także algorytm konstruowania tego obiektu i ewentualnie złożoność tego algorytmu.

Twierdzenie 1 Dla każdego wyrażenia regularnego można skonstruować niedeterministyczny automat skończony, który rozpoznaje j_{}ezyk opisany przez wyrażenie. Co wi_{}ecej, automat można dobrać tak, że |Q| ≤ 2|α|, gdzie α oznacza wyrażenie, a Q zbiór stanów automatu.

Dowód rozpoczniemy od lematu.

Lemat 2 Dla dowolnych automatów A = (Σ, Q^{A}, I^{A}, δ^{A}, F^{A}) i B = (Σ, Q^{B}, I^{B}, δ^{B}, F^{B}) można skonstruować automaty C, D i E, takie, że L(C) = L(A)∪L(B), L(D) = L(A)L(B) i L(E) = (L(A))^{∗}, przy czym |Q^{C}| ≤ |Q^{A}| + |Q^{B}|, |Q^{D}| ≤ |Q^{A}| + |Q^{B}|, |Q^{C}| ≤ |Q^{A}| + 1.

Dowód Lematu. Ograniczymy si_{}e tu do podania konstrukcji, dowód ich poprawności pozostawiaj _{}ac Czytelnikowi.

Możemy założyć, że zbiory stanów Q^{A} i Q^{B} s _{}a rozł _{}aczne.

Automat C Q^{C} = Q^{A} ∪ Q^{B}, I^{C} = I^{A} ∪ I^{B}, F^{C} = F^{A} ∪ F^{B}, δ^{C} = δ^{A} ∪ δ^{B}.

Automat D Q^{D} = Q^{A} ∪ Q^{B}, I^{D} = I^{A},

F^{D} = \{ \begin{matrix}F^{A} ∪ F^{B} & gdy I^{B} ∩ F^{B} ≠ ∅ \\ F^{B} & w przec. przyp. \end{matrix}

δ^{C} = δ^{A} ∪ δ^{B} ∪ {(q, σ, p) : q ∈ F^{A} ∧ (∃r ∈ I^{B})(r, σ, p) ∈ δ^{B}}.

Automat E Q^{E} = Q^{A} ∪{q̃}, gdzie q̃ jest nowym stanem, I^{E} = I^{A} ∪{q̃}, F^{E} = F^{A} ∪{q̃}, δ^{E} = δ^{A} ∪ {(q_{f}, σ, q) : q_{f} ∈ F ∧ (∃p ∈ I^{A})(p, σ, q) ∈ δ^{A}}.

Dowód Twierdzenia 1 prowadzimy przez indukcj_{}e ze wzgl_{}edu na złożoność wyrażenia regularnego, α. Dla α = ∅ lub α = σ, z łatwości _{}a można podać automat z dwoma stanami rozpoznaj _{}acy L[α]. Z kolei załóżmy, że mamy już automaty rozpoznaj _{}ace L[α] i L[β] o odpowiednio ≤ 2|α| i ≤ 2|β| stanach. Wówczas z lematu otrzymujemy

• automat dla L[(α + β)] o liczbie stanów ≤ 2|α| + 2|β| ≤ 2|(α + β)|, • automat dla L[(αβ)] o liczbie stanów ≤ 2|α| + 2|β| ≤ 2|(αβ)|,

• automat dla L[(α^{∗})] o liczbie stanów ≤ 2|α| + 1 ≤ 2|(α^{∗})|.

Na podstawie powyższych obserwacji nietrudno jest zaprojektować algorytm, który rekurencyjnie rozkłada wyrażenie regularne na wyrażenia prostsze, znajduje dla nich automaty, a nast_{}epnie syntetyzuje z nich automat dla wyrażenia oryginalnego za pomoc _{}a konstrukcji C,D lub E z dowodu Lematu 2. □

Pokażemy teraz, że transformacja odwrotna, tzn. automatu w wyrażenie regularne, jest również wykonalna, choć dowód jest tu nieco trudniejszy. Właśnie teraz wykorzystamy wprowadzone już wcześniej poj_{}ecie równania w algebrze j_{}ezyków.

Niech A = (Σ, Q, I, δ, F) b_{}edzie automatem. Dla każdego q ∈ Q, niech L(A, q) b_{}edzie zbiorem słow akceptowanych przez automat, który różni si_{}e od A co najwyżej tym, że jego jedynym stanem pocz _{}atkowym jest q, tzn.

L(A, q) = {w : (∃p ∈ F) q →^{w} p}

Z automatem A zwi _{}ażemy teraz pewien układ równań, E(A), w którym, jako niewiadomych używać b_{}edziemy zmiennych ze zbioru {X_{q} : q ∈ Q}. Jak si_{}e późniaj okaże, zbiory L(A, q) b_{}ed _{}a stanowić (jedyne) rozwi _{}azanie tego układu.

Niech q ∈ Q i niech δ(q) b_{}edzie zbiorem wszystkich przejść o pocz _{}atku q, tj. przejść postaci (q, σ, q′), q′ ∈ Q, σ ∈ Σ. Ponadto niech

Empty(q) = \{ \begin{matrix}ϵ & gdy q ∈ F \\ ∅ & w przec. przyp. \end{matrix}

Określamy równanie E(q) nast_{}epuj _{}aco. Jeśli zbiór przejść δ(q) jest pusty, to

E(q) : X_{q} = Empty(q)

jeśli zaś δ(q) = {(q, σ_{1}, q_{1}), …, (q, σ_{m}, q_{m})}, to

E(q) : X_{q} = σ_{q_{1}}X_{1} ∪ … ∪ σ_{m}X_{q_{m}} ∪ Empty(q)

Niech E(A) b_{}edzie zbiorem wszystkich otrzymanych w ten sposób równań,

E(A) = {E(q) : q ∈ Q}

Dowód nast_{}epuj _{}acego lematu pozostawiamy jako łatwe ćwiczenie.

Lemat 3 Podstawienie L(A, q) za X_{q}, dla q ∈ Q, jest rozwi _{}azaniem układu równań E(A) w dziedzinie P (Σ^{∗}). □

Ćwiczenie. Udowodnić, że opisane powyżej podstawienie jest jedynym rozwi _{}azaniem układu.

Możemy już udowodnić

Twierdzenie 2 Istnieje algorytm, który dla dowolnego automatu skończonego A, produkuje wyrażenie regularne opisuj _{}ace j_{}ezyk L(A).

Dowód. Niech E(A) b_{}edzie układem równań stowarzyszonym z A, określonym jak wyżej. Układ ten b_{}edziemy transformować do kolejnych postaci E(A) = E_{0}(A), E_{1}(A), …, E_{i}(A), …, zachowuj _{}ac nast_{}epuj _{}ace niezmienniki:

• dla każdego q ∈ Q, w układzie E_{i}(A) jest dokładnie jedno równanie, którego lew _{}a stron _{}a jest X_{q}, przy czym jest ono postaci

X_{q} = α_{1}X_{q_{1}} ∪ … ∪ α_{m}X_{q_{m}} ∪ β

gdzie α_{1}, …, α_{m}, β s _{}a wyrażeniami regularnymi nad Σ, oraz ϵ ∉ L[α_{i}], dla i = 1, …, m (zakładamy, że stany q_{1}, …, q_{m} s _{}a różne),

• podstawienie X_{q} ← L(A, q) jest rozwi _{}azaniem układu E_{i}(A), tzn. dla każdego równania, w opisanej wyżej postaci, równość

L(A, q) = L[α_{1}]L(A, q_{1}) ∪ … ∪ L[α_{m}]L(A, q_{m}) ∪ L[β]

jest spełniona.

Z Lematu 3 warunki te s _{}a spełnione przez pocz _{}atkowy układ E(A). Pokażemy, że po skończonej ilości kroków i przy zachowaniu niezmienników osi _{}agniemy układ, w którym każde równanie b_{}edzie w postaci rozwi _{}azanej, tzn. postaci X_{q} = β. Wobec drugiego niezmiennika otrzymamy L(A, q) = L[β].

Algorytm jest nast_{}epuj _{}acy (b_{}edziemy używali tutaj zmiennej E, której wartościami s _{}a układy równań):

Na starcie, E staje si_{}e układem E(A). Dalej, jeśli E nie jest jeszcze w postaci rozwi _{}azanej, wybieramy dowoln _{}a zmienn _{}a wyst_{}epuj _{}ac _{}a po prawej stronie któregoś z równań, powiedzmy X_{q}, i rozważamy równanie X_{q} = R. (Takie równanie jest w naszym układzie zgodnie z pierwszym niezmiennikiem.)

Z kolei rozważamy dwa przypadki.

• Jeżeli zmienna X_{q} wyst_{}epuje w R, to równanie to możemy przedstawić (używaj _{}ac przemienności ∪) X_{q} = αX_{q} ∪ R_{1}, gdzie R_{1} nie zawiera X_{q}. Wówczas zast_{}epujemy je równaniem X_{q} = (α^{∗})R_{1}, a nast_{}epnie na wszystkie wyst _{}apienia zmiennej X_{q} w pozostałych równaniach podstawiamy (α^{∗})R_{1}. W razie potrzeby, porz _{}adkujemy prawe strony równań, tak by każda zmienna wyst_{}epowała co najwyżej raz, używaj _{}ac prawa rozdzielności AX ∪ BX = (A + B)X, zapewniaj _{}ac w ten sposób pierwszy niezmiennik. Zauważmy, że po tym kroku zmienna X_{q} znikn_{}eła z prawych stron równań. Niezmiennik drugi jest spełniony przez nowe równanie X_{q} = (α^{∗})R_{1} na mocy Lematu Ardena, a dla pozostałych równań jest oczywist _{}a konsekwencj _{}a.

• Jeśli zmienna X_{q} nie wyst_{}epuje po prawej stronie równania X_{q} = R, to wszystkie wyst _{}apienia X_{q} na prawych stronach pozostałych równań zast_{}epujemy przez R. Podobnie jak poprzednio wykonujemy ewentualne porz _{}adkowanie dla utrzymania równań w standardowej postaci. (Również i po tej operacji, ilość zmiennych wyst_{}epuj _{}acych po prawej stronie równań zmniejszyła si_{}e o 1. Niezmienniki zostały oczywiście zachowane.)

Jak wynika z komentarzy poczynionych w trakcie opisu algorytmu, układ E osi _{}agnie w końcu postać rozwi _{}azan _{}a, {X_{q} = β_{q} : q ∈ Q}, i to po nie wi_{}ecej niż |Q| obrotach p_{}etli (za każdym razem, z prawych stron równań znika jedna zmienna). Niezmiennik drugi daje nam wi_{}ec przedstawienie L(A, q) = L[β_{q}], dla każdego q ∈ Q. Oczywiście,

L = ⋃_{q∈I} L[β_{q}]

poszukiwanym wyrażeniem regularnym dla L jest wi_{}ec ∑_{q∈I} β_{q}. □

Uwaga. Analiza powyższego algorytmu pokazuje, że konstruowane wyrażenie osi _{}aga rozmiar rz_{}edu 2^{O(|Q|)}. Najcz_{}eściej nie jest to wyrażenie najkrótsze. Jednak w pesymistycznych przypadkach, wyniku tego nie można poprawić^{2}.

Przykład 6 Rozważmy automat

[figure: q_{0}; 0; 1; q_{1}; 0; 1; q_{2}; 1; 0]

gdzie q_{0} jest stanem pocz _{}atkowym i akceptuj _{}acym. Automat ten rozpoznaje liczby podzielne przez 3 zapisane w systemie binarnym (dopuszczamy prefiks zer). Dokładniej, automat przyjmie stan q_{i} jeśli przeczytana dot _{}ad liczba daje reszt_{}e i z dzielenia przez 3.

Post_{}epuj _{}ac jak w dowodzie Twierdzenia 2, otrzymujemy najpierw układ równań

X_{q_{0}} = ε ∪ 0X_{q_{0}} ∪ 1X_{q_{1}}
X_{q_{1}} = 1X_{q_{0}} ∪ 0X_{q_{2}}
X_{q_{2}} = 0X_{q_{1}} ∪ 1X_{q_{2}}

Stosuj _{}ac krok algorytmu oparty na Lemacie Ardena do równania dla X_{q_{2}}, otrzymujemy

X_{q_{2}} = 1^{∗}0X_{q_{1}}

sk _{}ad po podstawieniu do równania dla X_{q_{1}} i ponownym uproszczeniu mamy

X_{q_{1}} = 1X_{q_{0}} ∪ 01^{∗}0X_{q_{1}}
= (01^{∗}0)^{∗}1X_{q_{0}}

sk _{}ad wreszcie

X_{q_{0}} = ε ∪ 0X_{q_{0}} ∪ 1(01^{∗}0)^{∗}1X_{q_{0}}
= ε ∪ (0 + 1(01^{∗}0)^{∗}1)X_{q_{0}}
= (0 + 1(01^{∗}0)^{∗}1)^{∗}

co daje nam poszukiwane wyrażenie.

2Zob. prac_{}e A. Ehrenheucht, P. Zeiger, Complexity Measures for Regular Expressions, Journal of Computer and System Science 12, 134–146 (1976).

Twierdzenia 1 i 2 możemy podsumować w nast_{}epuj _{}ac_{}ej równoważności.

Twierdzenie 3 (Kleene) J_{}ezyk jest rozpoznawalny przez automat skończony wtedy i tylko wtedy, gdy jest regularny.

Ćwiczenia

1. Skonstruować wyrażenia regularne reprezentuj _{}ace j_{}ezyki z przykładów 4 i 5.

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

3. (*) 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}

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

5. (*) 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.

6. Udowodnić wspomniane wyżej górne oszacowanie na rozmiar wyrażenia regularnego, jakie konstruuje algorytm z dowodu Twierdzenia 2.

2.4 Kryterium nieregularności

Jak wykazać, że jakiś j_{}ezyk nie jest regularny?

Matematyczny dowód nieistnienia jakiegoś obiektu (w naszym przypadku: automatu rozpoznaj _{}acego j_{}ezyk) wymaga cz_{}esto gł_{}ebokiej analizy problemu, nawet jeśli sam fakt wydaje si_{}e intuicyjnie oczywisty. Pomocne może być wskazanie jakiejś własności przysługuj _{}acej wszystkim j_{}ezykom regularnym — brak takiej własności wyklucza regularność j_{}ezyka.

Podamy teraz przykład takiej własności.

Lemat 4 (o pompowaniu) Niech A = (Σ, Q, I, δ, F) b_{}edzie automatem skończonym, |Q| = n. Jeśli automat akceptuje słowo w o długości |w| ≥ n, to istniej _{}a słowa w′, v, w′′, takie że w = w′vw′′, |w′v| ≤ n, v ≠ ϵ, oraz, dla każdego m = 0, 1, 2, …, w′v^{m}w′′ ∈ L(A).

Dowód. Przypuśćmy, że p →^{w} q, gdzie p ∈ I, q ∈ F i w = w_{1}w_{2} … w_{k}. Z charakteryzacji relacji δ̂ (Fakt 4), mamy przebieg

p = q_{0} →^{w_{1}} q_{1} →^{w_{2}} q_{2} … q_{k−2} →^{w_{k−1}} q_{k−1} →^{w_{k}} q_{k} = q

Jeśli teraz k ≥ |Q|, to istniej _{}a i, j, 1 ≤ i < j ≤ n, takie że q_{i} = q_{j}. Połóżmy w′ = w_{1} … w_{i} (ϵ, jeśli i = 0), v = w_{i+1} … w_{j}, w′′ = w_{j+1} … w_{k}. Oczywiście, założenia o długościach w′v i v s _{}a spełnione. Przyjmuj _{}ac q_{i} = q_{j} = q̃, mamy wi_{}ec p →^{w′} q̃, q̃ →^{u} q̃ i q̃ →^{w′′} q. St _{}ad, stosuj _{}ac ponownie charakteryzacj_{}e z Faktu 4, nietrudno otrzymać, że

p →^{w′w′′} q, a także p →^{w′vvw′′} q, p →^{w′vvvw′′} q, itd. , ogólnie p →^{w′v^{m}w′′} q, dla każdego m = 0, 1, . . ..

□

Zauważmy, że, z Lematu o pompowaniu, jeśli A akceptuje pewne słowo w o długości nie mniejszej niż n, to A akceptuje także słowo w′w′′, gdzie |w′w′′| < |w|. Stosuj _{}ac ten argument dostatecznie wiele razy, otrzymujemy nast_{}epuj _{}acy fakt.

Wniosek 1 Niech A = (Σ, Q, I, δ, F) b_{}edzie automatem skończonym, |Q| = n. Jeśli automat A akceptuje jakieś słowo, to również akceptuje pewne słowo o długości mniejszej niż n. □

Przykład 7 (dowód nieregularności) Niech Σ = {a, b} i L = {a^{n}b^{n} : n ∈ N}. J_{}ezyk L nie jest regularny. Istotnie, przypuśćmy przeciwnie, że L jest akceptowany przez automat o p stanach. Z Lematu o pompowaniu, słowo a^{p}b^{p} można przedstawić jako uvw′ gdzie |uv| ≤ p, a zatem u = a^{i}, v = a^{j} i w′ = a^{k}b^{p}, gdzie i + j + k = p, przy czym j > 0. Z tezy lematu, również słowo a^{i}a^{j}a^{j}a^{k}b^{p} = a^{p+j}b^{p} ∈ L, wbrew definicji j_{}ezyka L.

Ćwiczenia

1. Dowieść, że zbiór palindromów nie jest regularny.

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

3. 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}

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

nie jest regularny.

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

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

2.5 Problemy decyzyjne i algorytmy

Problem 1.

Dane: Automat A = (Σ, Q, I, δ, F) i słowo w ∈ Σ^{∗}, w = w_{1} … w_{k}. Pytanie: Czy w ∈ L(A)? Dla każdego σ ∈ Σ, określmy operacj_{}e na zbiorach stanów Y ⊆ Q

Step_{σ}(Y) = {q : (∃p ∈ Y)p →^{σ} q}

Rozważmy nast_{}epuj _{}acy algorytm:

Algorytm 1 Wejście: słowo w i automat A X := I; Dla i = 1, …, |w| wykonuj X := Step_{w_{i}}(X); Wynik: wartość logiczna relacji X ∩ F ≠ ∅

Nietrudno sprawdzić, że algorytm istotnie rozwi _{}azuje Problem 1. Dokładniej, po ikrotnym wykonaniu instrukcji p_{}etli, wartości _{}a zmiennej X jest zbiór {q : (∃p ∈ I)p →^{w_{1}...w_{i}} q}. Czas wykonania operacji Step_{σ} jest rz_{}edu O(|Q|^{2}), tak wi_{}ec łaczny czas działania algorytmu można oszacować^{3} przez O|(w||Q|^{2}).

3Lepszym oszacowaniem dla operacji Step jest |Q|m, gdzie m jest maksymaln _{}a liczb _{}a strzałek o danej etykiecie wychodz _{}acych z dowolnego stanu; wówczas łaczny czas działania algorytmu jest O(|w|m|Q|).

Problem 2.

Dane: Automat A = (Σ, Q, I, δ, F) i słowo w ∈ Σ^{∗}.

Pytanie: Czy w zawiera prefiks w L(A)?

Algorytm 2

Dane: słowo w i automat A

1. X := I; i := 0;

2. Dopóki (X ∩ F = ∅ ∧ i < |w|), wykonuj i := i + 1; X := Step_{w_{i}}(X);

Wynik: wartość logiczna relacji X ∩ F ≠ ∅

Po wykonaniu tego algorytmu, jeśli wynikiem jest prawda, a wartości _{}a zmiennej i jest ĩ, to w_{1} … wĩ jest pierwszym prefiksem w należ _{}acym do j_{}ezyka L(A).

Algorytm 2 znajduje zastosowanie w konkretnych sytuacjach, w których interesuje nas wyszukanie danego wzorca we wi_{}ekszym tekście, przy czym wzorzec może być zadany wyrażeniem regularnym. Sytuacja taka wyst_{}epuje w edytorach tekstu, pojawia si_{}e także w pierwszej fazie kompilowania, jak _{}a jest tzw. analiza leksykalna. Np. instrukcja zast _{}apienia w tekście bloków symboli b (“blank”) przez jeden symbol, wymaga najpierw znalezienia podsłów opisanych wyrażeniem b(b^{∗}). Przypuśćmy, że w tekście t szukamy wzorca opisanego wyrażeniem regularnym α. Problem sprowadza si_{}e do pytania, czy t zawiera prefiks należ _{}acy do j_{}ezyka (Σ)^{∗}L[α]. Na podstawie Twierdzenia 1, możemy skonstruować automat (niedetreministyczny) A o O(|α|) stanach, rozpoznaj _{}acy j_{}ezyk (Σ)^{∗}L[α]. Nast_{}epnie, wystarczy zastosować Algorytm 2 dla tego automatu i słowa t.^{4}

Bardzo naturalny jest tzw. problem niepustości, czyli jest pytanie, czy automat akceptuje w ogóle jakieś słowo.

Problem 3.

Dane: Automat A = (Σ, Q, I, δ, F)

Pytanie: Czy L(A) ≠ ∅?

Tym razem algorytm poprzedzimy dokładniejsz _{}a analiz _{}a problemu. Wygodnie b_{}edzie wprowadzić nast_{}epuj _{}ace poj_{}ecie. Powiemy, że stan q jest osi _{}agalny ze stanu p, jeśli istnieje w ∈ Σ^{∗}, takie że p →^{w} q. Podobnie, stan q jest osi _{}agalny ze zbioru stanów E, jeśli jest osi _{}agalny ze pewnego stanu p ∈ E. Zauważmy, że L(A) ≠ ∅ wtedy i tylko wtedy, gdy cz_{}eść wspólna zbioru F i zbioru stanów osi _{}agalnych z I jest niepusta. Wobec tego zadanie można sprowadzić do obliczenia tego ostatniego zbioru. W tym celu trzeba umieć, dla danych stanów p, q, rozstrzygn _{}ać, czy (∃w ∈ Σ^{∗}) p →^{w} q. (Jeżeli automat przedstawiamy jako graf, własność ta polega na istnieniu jakiejkolwiek ścieżki z wierzchołka p do q.) Pewna trudność wynika z faktu, że a priori nie ograniczamy tu długości słowa w. Jednakże, z lematu o pompowaniu (Lemat 4, por. także uwag_{}e przed Wnioskiem 1) wiemy już, że jeśli p →^{w} q, to istnieje v, |v| < |Q|, takie że p →^{v} q.

Niech teraz operacja Step działaj _{}aca na podzbiorach zbioru stanów Q b_{}edzie określona nast_{}epuj _{}aco:

4Nasze rozumowanie prowadzi do algorytmu działaj _{}acego w czasie O(|t||α|^{2}). W rzeczywistości, algorytm można ulepszyć do liniowego wzgl_{}edem |α|, tj. O(|t||α|), por. Aho, Hopcroft,Ullman, Projektowanie i analiza algorytmów komputerowych, PWN 1983, str.414.

Step(Y) = ⋃_{σ∈Σ} Step_{σ}(Y)

Możemy już przedstawić algorytm.

Algorytm 3

Dane: Automat A

1. X := ∅; X_{1} := I;

2. Dopóki (X_{1} ≠ ∅) wykonuj

3. X := X ∪ X_{1};

4. X_{1} := Step(X_{1}) \ X;

Wynik: wartość logiczna relacji X ∩ F ≠ ∅

Zauważmy, że linia 3 może być wykonana co najwyżej |Q| razy (za każdym razem dokładamy coś do X), zatem algorytm na pewno si_{}e zatrzymuje po wykonaniu nie wi_{}ecej niż |Q| obrotów p_{}etli 2. Dalej, nietrudno jest wykazać, przez indukcj_{}e ze wzgl_{}edu na k, k = 0, 1, …, że po k-krotnym wykonaniu p_{}etli 2, wartości _{}a zmiennej X jest zbiór wszystkich stanów, które s _{}a osi _{}agalne z I w mniej niż k krokach, tzn. zbiór {q : (∃p ∈ I)(∃w ∈ Σ^{∗})(p →^{w} q) ∧ |w| < k}, a wartości _{}a zmiennej X_{1} jest zbiór tych stanów, które s _{}a osi _{}agalne z I po raz pierwszy w dokładnie k krokach. Zatem, z wniosku z lematu o pompowaniu (Wniosek 1) wynika, że końcow _{}a wartości _{}a zmiennej X jest zbiór wszystkich stanów osi _{}agalnych z I, tzn. zbiór {q : (∃p ∈ I)(∃w ∈ Σ^{∗})p →^{w} q}.

Czas wykonania operacji Step jest rz_{}edu O(|Q|^{2}), tak wi_{}ec łaczny czas działania powyższego algorytmu można oszacować przez O(|Q|^{3}). Przedstawiliśmy ten algorytm ze wzgl_{}edu na jego prosty schemat; nie jest to jednak algorytm optymalny. Czytelnik zauważył być może, że zamiast obliczania kolejnych iteracji funkcji Step, możemy po prostu przeszukiwać graf automatu algorytmem przeszukiwania wgł _{}ab (DFS), nie zwracaj _{}ac uwagi na etykiety kraw_{}edzi, dopóki nie na trafimy na stan akceptuj _{}acy. Osi _{}agamy w ten sposób złożoność O(|Q| + |δ|).

Problem 4.

Dane: Automat A = (Σ, Q, I, δ, F)

Pytanie: Czy L(A) jest nieskończony?

Wybieramy jedno z kilku możliwych podejść do tego problemu.

Powiemy, że stan p jest produktywny, jeśli jakiś stan akceptuj _{}acy q ∈ F jest osi _{}agalny z p.

Powiemy, że stan p jest ściśle produktywny, jeśli jakiś stan akceptuj _{}acy q ∈ F jest osi _{}agalny z p poprzez słowo niepuste (tj. (∃q ∈ F)(∃w ≠ ϵ) p →^{w} q ).

Zauważmy, że stan produktywny a nie ściśle produktywny musi być akceptuj _{}acy.

Zbiór stanów produktywnych można wyznaczyć stosuj _{}ac wariant algorytmu 3 dla automatu dualnego A^{−1}, tj. automatu z odwrócon _{}a relacj _{}a przejścia

(q, σ, p) ∈ δ^{−1} ⇔ (p, σ, q) ∈ δ

Nietrudno zauważyć, że zbiór stanów produktywnych automatu A to zbiór stanów osi _{}agalnych z F w automacie A^{−1}. Zbiór stanów ściśle produktywnych można wyznaczyć bardzo podobnie (rozważaj _{}ac, zamiast F, stany “o jeden krok przed F ”); szczegóły pozostawiamy Czytelnikowi.

Z kolei powiemy, że stan p jest ograniczony jeśli zbiór {w ∈ Σ^{∗} : (∃q ∈ F)p →^{w} q} jest skończony. Oczywiście, L(A) jest nieskończony wtedy i tylko wtedy, gdy przynajmniej jeden stan w I nie jest ograniczony. Zadanie sprowadza si_{}e wi_{}ec do wyznaczenia zbioru stanów ograniczonych i porównania go z I.

Wygodnie b_{}edzie wprowadzić operacj_{}e w pewnym sensie dualn _{}a do operacji Step,

BackStep(Y) = {p : (∀σ ∈ Σ)(∀q ∈ Q)(p →^{σ} q) ⇒ q ∈ Y }

Poniższy algorytm, strukturalnie bardzo podobny do Algorytmu 3, oblicza zbiór stanów ograniczonych automatu A i odpowiada na pytanie, czy L(A) jest nieskończony. Zakładamy przy tym, na podstawie uwag powyżej, że mamy już procedur_{}e wyznaczaj _{}ac _{}a zbiór stanów ściśle produktywnych.

Algorytm 4

Dane: Automat A

1. X := ∅; X_{1} := zbiór stanów, które nie s _{}a ściśle produktywne;

2. Dopóki (X_{1} ≠ ∅) wykonuj

3. X := X ∪ X_{1};

4. X_{1} := BackStep(X_{1}) \ X;

Wynik: wartość logiczna relacji ¬(I ⊆ X)

Tu również, podobnie jak w algorytmie 3, linia 3 może być wykonana co najwyżej |Q| razy, zatem algorytm na pewno si_{}e zatrzymuje po wykonaniu nie wi_{}ecej niż |Q| obrotów p_{}etli 2. Dalej, przez indukcj_{}e ze wzgl_{}edu na k, k = 0, 1, …, można wykazać, że po kkrotnym wykonaniu p_{}etli 2, wartości _{}a zmiennej X jest zbiór tych stanów p, że każde słowo akceptowane z tego stanu (tzn. takie słowo w, że p →^{w} q dla pewnego q ∈ F) jest długości mniejszej niż k, podczas gdy wartości _{}a zmiennej X_{1} jest zbiór tych stanów p, że najdłuższe słowo akceptowane z p ma długość dokładnie k. Zatem, wartości _{}a końcow _{}a zmiennej X jest zbiór tych stanów p, że najdłuższe słowo akceptowane z tego stanu ma długość mniejsz _{}a niż |Q|. Z lematu o pompowaniu wiemy jednak, że jeśli z jakiegoś stanu automat akceptuje słowo o długości równej lub wi_{}ekszej od |Q|, to akceptuje z tego stanu nieskończenie wiele słów. Tak wi_{}ec, wartości _{}a końcow _{}a zmiennej X w naszym algorytmie jest dokładnie zbiór stanów ograniczonych automatu A.

Tu również czas działania algorytmu można oszacować przez O(|Q|^{3}). Ulepszenie algorytmu pozostawiamy Czytelnikowi.

Ćwiczenia

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

2. 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.

Literatura

• A.V.Aho, J.E.Hopcroft, J.D.Ullman, Projektowanie i analiza algorytmów komputerowych, w serii: Biblioteka Informatyki, Państwowe Wydawnictwo Naukowe, Warszawa 1983.

• J.E.Hopcroft, J.D.Ullman, Wprowadzenie do teorii automatów, j_{}ezyków i obliczeń, Wydawnictwo Naukowe PWN, Warszawa 1994.

• A.Blikle, Automaty i gramatyki. Wst_{}ep do lingwistyki matematycznej, Państwowe Wydawnictwo Naukowe, Warszawa 1971.

• T.H.Cormen, Ch.E.Leiserson, R.L.Rivest, Wprowadzenie do algorytmów, Wydawnictwa Naukowo–Techniczne, Warszawa 1998.