J_{}ezyki, Automaty i Obliczenia. Odcinek 2

Optymalizacja automatu skończonego. Własności j_{}ezyków regularnych.

Damian Niwiński

Październik 1996

1 Optymalizacja automatu skończonego

1.1 Determinizacja

O automatach A i B powiemy, że s _{}a równoważne, jeśli akceptuj _{}a ten sam j_{}ezyk, tzn. L(A) = L(B).

Automat A = (Σ, Q, I, δ, F) nazwiemy deterministycznym, jeśli ma on dokładnie jeden stan pocz _{}atkowy, a relacja δ jest dobrze określon _{}a funkcj _{}a z Q × Σ w Q, tzn., dla każdych q, σ, istnieje dokładnie jedno q′ takie, że (q, σ, q′) ∈ δ. W takim przypadku możemy pisać δ(q, σ) = q′ zamiast (q, σ, q′) ∈ δ. Podobnie, jeśli zbiór stanów pocz _{}atkowych jest singletonem, powiedzmy, I = {q_{I}}, to zwykle opuszczamy nawiasy {}, przedstawiaj _{}ac automat A = (Σ, Q, q_{I}, δ, F).

Zauważmy, że w automacie deterministycznym, dla każdego stanu q i każdego słowa w, istnieje dokładnie jeden przebieg automatu na słowie w startuj _{}acy ze stanu q; w szczególności istnieje dokładnie jedno obliczenie automatu na w (tj. przebieg startuj _{}acy ze stanu pocz _{}atkowego). Tak wi_{}ec, również relacja δ̂ (okrełona w Odcinku 1, w punkcie 2.2) jest wtedy funkcj _{}a, δ̂ : Q × Σ^{∗} → Q, która ponadto spełnia nast_{}epuj _{}ace równania rekurencyjne

δ̂(q_{I}, ϵ) = q_{I}  (1)
δ̂(q_{I}, wσ) = δ(δ̂(q_{I}, w), σ)  (2)

O deterministycznym automacie skończonym możemy myśleć jak o maszynie realizuj _{}acej pewien algorytm, mianowicie algorytm rozpoznawania słów j_{}ezyka L(A).

Przykład 1 Niech Σ = {0, 1, …, 9} i niech L b_{}edzie zbiorem słów stanowi _{}acych przedstawienia w systemie dziesi_{}etnym liczb podzielnych przez 3. J_{}ezyk ten jest rozpoznawany przez nast_{}epuj _{}acy automat A = (Σ, Q, s, δ, F).

• Q = {s, q_{0}, q_{1}, q_{2}}

• q_{I} = s • δ(s, d) = q_{d mod 3}, δ(q_{i}, d) = q_{(i+d) mod 3}, dla d ∈ Σ, i = 0, 1, 2

• F = {q_{0}}

ćwiczenie. Uogólnić powyższy przykład, konstruuj _{}ac automat dla j_{}ezyka L_{k,m}, złożonego ze słów, które w systemie o podstawie k reprezentuj _{}a liczby naturalne podzielne przez m.

Twierdzenie 1 Dla każdego automatu skończonego o n stanach, można skonstruować równoważny mu automat deterministyczny o nie wi_{}ecej niż 2^{n} stanach.

Dowód. Niech A = (Σ, Q, I, δ, F) b_{}edzie dowolnym niedeterministycznym automatem skończonym. Idea jest nast_{}epuj _{}aca: deterministyczny automat A′ symuluj _{}acy A powinien, w miar_{}e czytania kolejnych liter słowa w mieć informacj_{}e o wszystkich stanach, do jakich mógłby dojść w tym miejscu automat A. Zauważmy, że jeśli już mamy tak _{}a informacj_{}e dla jakiegoś słowa w, to nietrudno j _{}a “zaktualizować” dla przedłużenia w o liter_{}e σ ∈ Σ, wσ, itd.

Dokładniej, określamy deterministyczny automat A′ = (Σ, P (Q), I, δ′, F′), którego stanami s _{}a zbiory stanów automatu A, stanem pocz _{}atkowym jest zbiór stanów pocz _{}atkowych automatu A, oraz

• δ′(X, σ) = {q : (∃p ∈ X)(p, σ, q) ∈ δ}, dla X ∈ P (Q), σ ∈ Σ.

• F′ = {X : X ∩ F ≠ ∅}

Dla dowodu, że L(A′) = L(A), wystarczy pokazać, że

dla każdego w ∈ Σ^{∗}, δ̂′(I, w) = {q ∈ Q : (∃p ∈ I)p →^{w} q}

Stosuj _{}ac dla funkcji δ̂′ równania rekurencyjne (1) i (2) ze str. 1, otrzymujemy

δ̂′(I, ϵ) = I
= {q ∈ Q : (∃p ∈ I)p →^{ϵ} q}

oraz

δ̂′(I, wσ) = δ′(δ̂′(I, w), σ)
= {q : (∃q′ ∈ δ̂′(I, w))(q′, σ, q) ∈ δ}

(z definicji δ′)

= {q : (∃q′ ∈ Q, ∃p ∈ I)p →^{w} q′ →^{σ} q}

( z zalożenia indukcyjnego)

= {q : (∃p ∈ I)p →^{wσ} q}

Ta uwaga kończy dowód. □

Udowodnione przed chwil _{}a twierdzenie zastosujemy do wykazania ważnej własności klasy j_{}ezyków regularnych.

Twierdzenie 2 Rodzina j_{}ezyków regularnych nad alfabetem Σ jest zamkni_{}eta na operacje binarnej sumy, przeci_{}ecia (tzn. cz_{}eści wspólnej) i różnicy.

Dowód. Zamkni_{}etość na sum_{}e wynika wprost z definicji. Ze wzgl_{}edu na zależności pomi_{}edzy pozostałymi operacjami, wystarczy wykazać, że uzupełnienie Σ^{∗} − L j_{}ezyka regularnego L jest j_{}ezykiem regularnym. Niech L = L(A) dla deterministycznego automatu A = (Σ, Q, I, δ, F). Tworzymy automat A′, który różni si_{}e od A tylko tym, że rol_{}e stanów akceptuj _{}acych przejmuj _{}a teraz stany nie-akceptuj _{}ace A, tzn. F′ = Q − F. Nietrudno sprawdzić, że L(A′) = Σ^{∗} − L. □

1.2 Twierdzenie Myhilla-Nerode’a

Widzieliśmy już do tej pory, że j_{}ezyk regularny może być określony na różne sposoby: poprzez wyrażenie regularne, poprzez niedeterministyczny automat skończony i wreszcie, poprzez deterministyczny automat skończony. Udowodnimy teraz bardzo ważne twierdzenie, ukazuj _{}ace, że regularność j_{}ezyka może być scharakteryzowana poprzez cechy strukturalne samego j_{}ezyka, bez odwoływania si_{}e do “obiektów z zewn _{}atrz”, takich jak wyrażenia regularne lub automaty. Niejako produktem ubocznym tego twierdzenia b_{}edzie konstrukcja automatu deterministycznego o minimalnej liczbie stanów.

Dla dowolnego j_{}ezyka L ⊆ Σ^{∗}, określamy binarn _{}a relacj_{}e ∼_{L} na Σ^{∗} nast_{}epuj _{}aco: dla każdych u, w ∈ Σ^{∗}

u ∼_{L} w ⇔_{def} {u}^{−1}L = {w}^{−1}L
⇔ (∀v ∈ Σ^{∗})(uv ∈ L ⇔ wv ∈ L)

ćwiczenie. Sprawdzić, że ∼_{L} jest relacj _{}a równoważności.

Klas_{}e abstrakcji słowa w w relacji ∼_{L} b_{}edziemy oznaczać [w]_{L}. Odnotujmy dwie użyteczne własności relacji ∼_{L}.

Lemat 1 1. (∀u, w ∈ Σ^{∗})(∀σ ∈ Σ)u ∼_{L} w ⇒ uσ ∼_{L} wσ

2. L = ⋃_{w∈L}[w]_{L} □

Dowód. Punkt pierwszy wynika łatwo z definicji relacji ∼_{L}. W punkcie 2, inkluzja “⊆” jest oczywista. Dla dowodu inkluzji przeciwnej, wystarczy wykazać, że w ∼ u i w ∈ L implikuje u ∈ L, co wynika z definicji ∼_{L} przy v = ϵ. □

Indeksem relacji równoważności nazywamy liczb_{}e jej klas abstrakcji.

Przykład 2 Niech Σ = {0, 1}. Niech #_{x}(w) oznacza liczb_{}e wyst _{}apień symbolu x w słowie w. (a) Niech L b_{}edzie zbiorem ci _{}agów o parzystej ilości jedynek. Wówczas u ∼_{L} w wtedy i tylko wtedy, gdy #_{1}(u) ≡ #_{1}(w) (mod 2). Indeks relacji ∼_{L} jest równy 2. (b) Niech M b_{}edzie zbiorem słów v, w których #_{0}(v) = #_{1}(v). Wówczas u ∼_{M} w wtedy i tylko wtedy, gdy #_{1}(u) − #_{0}(u) = #_{1}(w) − #_{0}(w). Indeks relacji ∼_{M} jest nieskończony.

Twierdzenie 3 (Myhill-Nerode) Niech L ⊆ Σ^{∗}. Nast_{}epuj _{}ace warunki s _{}a równoważne:

• relacja ∼_{L} ma skończony indeks;

• j_{}ezyk L jest regularny.

Ponadto, jeżeli warunki te zachodz _{}a, to indeks relacji ∼_{L} jest równy minimalnej liczbie stanów, jak _{}a musi mieć automat deterministyczny rozpoznaj _{}acy j_{}ezyk L.

Dowód.

“wtedy” Niech L = L(A), gdzie A = (Σ, Q, q_{I}, δ, F) jest deterministycznym automatem skończonym. Określamy relacj_{}e ∼_{A} na Σ^{∗},

u ∼_{A} w ⇔ δ̂(q_{I}, u) = δ̂(q_{I}, w)

Oczywiście, ta relacja jest równoważności _{}a o indeksie nie wi_{}ekszym niż |Q|. Z drugiej strony, pokażemy, że ∼_{A}⊆∼_{L}. Istotnie, jeśli δ̂(q_{I}, u) = δ̂(q_{I}, w) i x ∈ Σ^{∗} jest dowolnym słowem, to δ̂(q_{I}, ux) = δ̂(q_{I}, wx), a zatem ux ∈ L ⇔ wx ∈ L.

Z inkluzji ∼_{A}⊆∼_{L} wynika, że indeks ∼_{L} jest niewi_{}ekszy^{1} niż indeks ∼_{A}, a zatem, tym bardziej niewi_{}ekszy od liczby stanów automatu A.

“tylko wtedy” Przypomnijmy, że [u]_{L} oznacza klas_{}e abstrakcji słowa u w relacji ∼_{L}. Określamy deterministyczny automat A^{L} = (Σ, Q^{L}, q_{I}^{L}, δ^{L}, F^{L}) nast_{}epuj _{}aco:

• Q^{L} = {[u]_{L} : u ∈ Σ^{∗}}

• q_{I}^{L} = [ϵ]_{L}

• δ^{L}([u]_{L}, σ) = [uσ]_{L}

• F^{L} = {[u]_{L} : u ∈ L}

Z lematu o relacji ∼_{L} wynika, że funkcja δ^{L} jest dobrze określona oraz, że [w]_{L} ∈ F ⇔ w ∈ L. Zauważmy, że liczba stanów automatu A^{L} jest równa indeksowi relacji ∼_{L}.

Dla dowodu, że L(A^{L}) = L, wystarczy wi_{}ec wykazać, że dla każdego w ∈ Σ^{∗},

δ̂^{L}(q_{I}, w) = [w]_{L}

Argument przebiega przez indukcj_{}e ze wzgl_{}edu na długość w. Stosuj _{}ac równania rekurencyjne (1) i (2) ze str. 1 dla δ̂^{L}, otrzymujemy

• δ̂^{L}(q_{I}, ϵ) = q_{I} = [ϵ]_{L},

• δ̂^{L}(q_{I}, wσ) = δ^{L}(δ̂^{L}(q_{I}, w), σ) = δ^{L}([w]_{L}, σ) = [wσ]_{L}

□ Pytanie. Czy rozumowanie z powyższego dowodu można rozszerzyć na przypadek dowolnego automatu niedeterministycznego i tym samym udowodnić, że indeks ∼_{L} jest niewi_{}ekszy od liczby stanów dowolnego automatu skończonego rozpoznaj _{}acego L?

1Jeżeli r, s s _{}a równoważnościami na tym samym zbiorze i r ⊆ s, to klasy abstrakcji relacji s s _{}a sumami klas abstrakcji relacji r.

1.3 Automat minimalny

W poprzednim punkcie wykazaliśmy, że spośród wszystkich automatów deterministycznych akceptuj _{}acych j_{}ezyk regularny L, automat A^{L} opisany w dowodzie Twierdzenia Myhilla-Nerode’a ma ma minimaln _{}a możliw _{}a liczb_{}e stanów.

Obecnie zastanowimy si_{}e nad możliwości _{}a skonstruowania automatu A^{L}. Zauważmy, że automat ten zdefiniowaliśmy odołuj _{}ac si_{}e do relacji ∼_{L}, o której wiemy, że istnieje, ale która a priori nie jest nam znana, nawet jeśli mamy dane wyrażenie regularne lub automat rozpoznaj _{}acy j_{}ezyk L. W konkretnych przypadkach, możemy cz_{}esto t_{}e relacj_{}e “odgadn _{}ać” i przy jej pomocy zbudować automat A^{L} (tak b_{}edzie w wi_{}ekszości zadań). Jednakże nie jest to metoda dostatecznie ogólna. Zobaczymy wszakże, że automat A^{L} można zawsze otrzymać z dowolnego automatu deterministycznego rozpoznaj _{}acego L poprzez “sklejenie” niektórych jego stanów.

Potrzebne nam b_{}edzie uściślenie poj_{}ecia “sklejania” a także jasne kryterium, kiedy można utożsamiać dwa automaty. Poniższe poj_{}ecia można wprowadzić w przypadku ogólnym, jednak dla naszych potrzeb wystarczy rozważać automaty deterministyczne.

Izomorfizm. Intuicyjnie, powinno być oczywiste, że możemy utożsamić automaty, które różni _{}a si_{}e jedynie nazwami stanów. Bardziej dokładnie, niech A = (Σ, Q, q_{I}, δ, F) i B = (Σ, Q′, q′_{I}, δ′, F′) b_{}ed _{}a automatami deterministycznymi nad tym samym alfabetem Σ, takimi, że |Q| = |Q′|. Funkcj_{}e bijekcj_{}e h : Q → Q′ nazywamy izomorfizmem z A w B, jeśli

• h(q_{I}) = q′_{I}

• (∀q, q′ ∈ Q)(∀σ ∈ Σ) h(δ(q, σ)) = δ′(h(q), σ)

• (∀q ∈ Q) q ∈ F ⇔ h(q) ∈ F′

Zauważmy, że jeśli h jest izomorfizmem z A w B, to funkcja odwrotna h^{−1} : Q′ → Q jest izomorfizmem z B w A.

Jeśli istnieje izomorfizm z A w B, to o automatach A i B mówimy, że s _{}a izomorficzne lub, że s _{}a równe z dokładności _{}a do izomorfizmu.

Lemat 2 Jeśli automat deterministyczny A rozpoznaj _{}acy j_{}ezyk L ma tyle samo stanów, co automat A^{L}, to jest z nim izomorficzny.

Dowód. Niech L = L(A), gdzie A = (Σ, Q, q_{I}, δ, F) jest automatem deterministycznym i niech A^{L} b_{}edzie automatem skonstruowanym w dowodzie Twierdzenia Myhilla-Nerode’a, przy czym zakładamy, że |Q| = |Q^{L}|.

Przypomnijmy poj_{}ecie relacji ∼_{A} jakie zdefiniowaliśmy w tymże dowodzie (str. 4) :

u ∼_{A} w ⇔ δ̂(q_{I}, u) = δ̂(q_{I}, w)

Jak zauważyliśmy wówczas, zachodzi inkluzja ∼_{A}⊆∼_{L}, przy czym indeks relacji ∼_{A} jest wi_{}ekszy lub równy od indeksu relacji ∼_{L} a mniejszy lub równy od liczby stanów automatu A. Jeśli jednak, jak zakładamy, te skrajne wartości s _{}a równe, to relacje ∼_{A} i ∼_{L} maj _{}a ten sam indeks i, wobec jednej inkluzji, muśz _{}a być równe, tzn.

(∗) δ̂(q_{I}, u) = δ̂(q_{I}, w) ⇔ u ∼_{L} w

Wykażemy teraz, że funkcja h : Q^{L} → Q, określona

h : [w]_{L} ↦ δ̂(q_{I}, w)

jest izomorfizmem automatów w sensie określonym powyżej.

Zauważmy najpierw, że z równoważności (*) wynika, iż

1. funkcja h jest dobrze określona, tzn. nie zależy od wyboru reprezentanta w ∈ [w]_{L};

2. funkcja h jest różnowartościowa.

Wobec założonej równoliczności zbiorów Q i Q^{L} dowodzi to, że funkcja ta jest bijekcj _{}a. Oczywiście h([ϵ]_{L}) = δ̂(q_{I}, ϵ) = q_{I}. Z kolei, mamy

h(δ^{L}([w]_{L}, σ)) = h([wσ]_{L})
= δ̂(q_{I}, wσ)
= δ(δ̂(q_{I}, w), σ)
= δ(h([w]_{L}), σ)

Wreszcie, dla każdego w ∈ Σ^{∗},

[w]_{L} ∈ F^{L} ⇔ w ∈ L
⇔ δ̂(q_{I}, w) ∈ F
⇔ h([w]_{L}) ∈ F

Wykazaliśmy, że funkcja h jest izomorfizmem automatów A i A^{L}. □

Konstrukcja automatu ilorazowego. Niech A = (Σ, Q, q_{I}, δ, F) b_{}edzie automatem deterministycznym i niech r b_{}edzie dowoln _{}a relacj _{}a równoważności na zbiorze jego stanów Q. Klasy abstrakcji relacji r b_{}edziemy oznaczać [q]_{r}. Intuicyjnie, relacja r “skleja” mi_{}edzy sob _{}a niektóre stany automatu A, co prowadzi do konstrukcji nowego automatu, który jednak na ogół nie musi być deterministyczny ani równoważny wyjściowemu. Podamy jednak warunki, które gwarantuj _{}a poprawność operacji sklejania.

Powiemy mianowicie, że relacja równoważności r ⊆ Q × Q jest kongruencj _{}a^{2}, jeśli

1. (∀q, q′) (q, q′) ∈ r ∧ q ∈ F ⇒ q′ ∈ F

2Termin jest wzi_{}ety z algebry. Jak wiadomo relacja na uniwersum algebry jest nazywana kongruencj _{}a, jeśli jest niezmiennicza ze wzgl_{}edu na operacje lub, co jest równoważne, jeśli jest j _{}adrem pewnego homomorfizmu.

2. (∀q, q′)(∀σ) (q, q′) ∈ r ⇒ (δ(q, σ), δ(q′, σ)) ∈ r

Jeśli relacja r jest kongruencj _{}a, to określamy automat ilorazowy

A/r = (Σ, Q_{r}, [q_{I}]_{r}, δ_{r}, F_{r})

gdzie Q_{r} = {[q]_{r} : q ∈ Q}, F_{r} = {[q]_{r} : q ∈ F }, a δ_{r} : Q_{r} × Σ → Q_{r} jest określona przez

(∀q ∈ Q)(∀σ ∈ Σ) δ_{r}([q]_{r}, σ) = [δ(q, σ)]_{r}

Zauważmy, że z warunku 2 wynika, że δ_{r} jest istotnie dobrze określon _{}a funkcj _{}a, tzn. jej definicja nie zależy od wyboru reprezentanta klasy abstrakcji [q]_{r}. Tak wi_{}ec, A/r jest również automatem deterministycznym.

Lemat 3 L(A/r) = L(A).

Dowód. Wykażemy przez indukcj_{}e ze wzgl_{}edu na długość słowa w ∈ Σ^{∗}, że

δ̂_{r}([q_{I}]_{r}, w) = [δ̂(q_{I}, w)]_{r}

Ponieważ, z definicji zbioru F_{r} oraz z pierwszego warunku definicyjnego kongruencji mamy [δ̂(q_{I}, w)]_{r} ∈ F_{r} wtedy i tylko wtedy, gdy δ̂(q_{I}, w) ∈ F, powyższa równość wystarczy do dowodu równości L(A/r) = L(A).

Z równań rekurencyjnych (1) i (2) ze str. 1 zastosowanych dla funkcji δ̂_{r}, otrzymujemy najpierw

δ̂_{r}([q_{I}]_{r}, ϵ) = [q_{I}]_{r}

a nast_{}epnie

δ̂_{r}([q_{I}]_{r}, wσ) = δ_{r}(δ̂_{r}([q_{I}]_{r}, w), σ)
= δ_{r}([δ̂(q_{I}, w)]_{r}, σ)

(z założenia indukcyjnego)

= [δ(δ̂(q_{I}, w), σ)]_{r}

(z definicji δ_{r})

= [δ̂(q_{I}, wσ)]_{r}

Ta uwaga kończy dowód. □

Aby z dowolnego automatu deterministycznego rozpoznaj _{}acego j_{}ezyk L otrzymać metod _{}a konstrukcji ilorazowej automat A^{L}, potrzebny jest jeszcze drobny zabieg techniczny: eliminacja stanów, które nie mog _{}a być osi _{}agni_{}ete ze stanu pocz _{}atkowego.

Niech A = (Σ, Q, q_{I}, δ, F) b_{}edzie automatem deterministycznym. Stanem osi _{}agalnym automatu nazwiemy każdy stan osi _{}agalny ze stanu pocz _{}atkowego q_{I}, tzn. taki, że q_{I} →^{w} q, dla pewnego w (por. Odcinek 1, punkt 2.5). Zauważmy, że stany nieosi _{}agalne nie wyst_{}epuj _{}a w żadnym obliczeniu automatu A. Mówi _{}ac z grubsza, możemy je bez szkody “wyrzucić” z automatu.

Bardziej dokładnie, niech Q_{o} b_{}edzie zbiorem stanów osi _{}agalnych automatu A. Określamy automat A_{red} (od ang. reduced) nast_{}epuj _{}aco:

A_{red} = (Σ, Q_{o}, q_{I}, δ_{red}, F ∩ Q_{o})

gdzie δ_{red} = δ ∩ Q_{o} × Σ × Q_{o}.

Nast_{}epuj _{}acy fakt pozostawiamy jako łatwe ćwiczenie.

Lemat 4 A_{red} jest automatem deterministycznym i L(A_{red}) = L(A). □

Twierdzenie 4 Niech L ⊆ Σ^{∗} b_{}edzie j_{}ezykiem regularnym, niech A^{L} b_{}edzie automatem skonstruowanym w dowodzie twierdzenia Myhilla-Nerode’a i niech A b_{}edzie dowolnym automatem deterministycznym rozpoznaj _{}acym j_{}ezyk L. Niech A_{red} b_{}edzie automatem otrzymanym z A przez eliminacj_{}e stanów nieosi _{}agalnych, tak jak to opisaliśmy powyżej. Wówczas istnieje kongruencja r na zbiorze stanów automatu A_{red}, taka, że automat ilorazowy A_{red}/r jest izomorficzny z A^{L}.

Dowód. Dla uproszczenia notacji, załóżmy, że A jest już w postaci zredukowanej, tzn. A_{red} = A = (Σ, Q, q_{I}, δ, F). Określmy relacj_{}e ∼⊆ Q × Q przez

q ∼ q′ ⇔ L(A, q) = L(A, q′)

(Przypomnijmy, Odcinek 1, punkt 2.3, że L(A, q) = {w : (∃p ∈ F) q →^{w} p}.) Oczywiście ∼ jest relacj _{}a równoważności. Aby wykazać, że jest także kongruencj _{}a, trzeba sprawdzić iż spełnia warunki definicyjne (por. str. 6), a mianowicie

1. q ∼ q′ ⇒ (q ∈ F ⇔ q′ ∈ F)

2. q ∼ q′ ⇒ (∀σ ∈ Σ)δ(q, σ) ∼ δ(q′, σ)

Pierwsza własność wynika z faktu, że q ∈ F ⇔ ϵ ∈ L(A, q). Dla dowodu drugiej, przypuśćmy, że q ∼ q′ i niech σ ∈ Σ. Niech δ(q, σ) = p i δ(q′, σ) = p′. Potrzebujemy udowodnić

L(A, p) = L(A, p′)

Przypuśćmy, że w ∈ L(A, p), zatem σw ∈ L(A, q) = L(A, q′). Odwołuj _{}ac si_{}e do poj_{}ecia obliczenia jako ci _{}agu przejść (por. Odcinek 1, Fakt 4), otrzymujemy q′ →^{σ} q′′ →^{w} q_{f}, dla pewnego q′′ ∈ Q i q_{f} ∈ F, ale ponieważ A jest automatem deterministycznym, wi_{}ec q′′ = p′, czyli w ∈ L(A, p′). W ten sposób stwierdziliśmy, że L(A, p) ⊆ L(A, p′), z symetrii wynika, że L(A, p) = L(A, p′), a zatem p ∼ p′.

Tak wi_{}ec, relacja ∼ jest kongruencj _{}a i z Lematu 3 wynika, że A/ ∼ jest deterministycznym automatem rozpoznaj _{}acym j_{}ezyk L. Pozostaje udowodnić, że A/ ∼ jest izomorficzny z A^{L}. Na podstawie Lematu 2, wystarczy udowodnić, że liczba stanów automatu A/ ∼ jest równa indeksowi relacji ∼_{L}.

Zanim przyst _{}apimy do właściwego dowodu, zrobimy pewn _{}a obserwacj_{}e, jaka wynika wprost z przyj_{}etych definicji.

(*) Jeśli q_{I} →^{w} q, to L(A, q) = {w}^{−1}L

Określmy teraz funkcj_{}e f : Q^{L} → Q_{∼} nast_{}epuj _{}aco:

(∀w ∈ Σ^{∗}) f([w]_{L}) = [δ̂(q_{I}, w)]_{∼}

Odnotujmy najpierw, że z (*) wynika, że funkcja f jest dobrze określona, tzn. w ∼_{L} v ⇒ δ̂(q_{I}, w) ∼ δ̂(q_{I}, v). (Istotnie, w ∼_{L} v implikuje, że {w}^{−1}L = {v}^{−1}Ls, co, wobec (*) implikuje L(A, δ̂(q_{I}, w)) = L(A, δ̂(q_{I}, v), sk _{}ad δ̂(q_{I}, w) ∼ δ̂(q_{I}, v).)

Z kolei wykażemy, że funkcja f jest różnowartościowa. Istotnie, h([w]_{L}) = h([v]_{L}) oznacza, że δ̂(q_{I}, w) ∼ δ̂(q_{I}, v), czyli L(A, δ̂(q_{I}, w)) = L(A, δ̂(q_{I}, v), co wobec (*) implikuje że {w}^{−1}L = {v}^{−1}L, a wi_{}ec [w]_{L} = [v]_{L}.

Wreszcie, z faktu, że wszystkie stany automatu A s _{}a osi _{}agalne, wynika, że funkcja f jest na zbiór Q_{∼}.

Ta uwaga kończy dowód twierdzenia. □

Wniosek 1 Spośród wszystkich automatów deterministycznych akceptuj _{}acych j_{}ezyk regularny L, automat A^{L} skonstruowany w dowodzie Twierdzenia Myhilla–Nerode’a ma minimaln _{}a ilość stanów, równ _{}a indeksowi relacji ∼_{L}. Ponadto, jeśli jakiś automat deterministyczny rozpoznaj _{}acy j_{}ezyk L ma tyle samo stanów co A^{L}, to jest z nim izomorficzny. □

Jest wi_{}ec w pełni uzasadnione, że automat A^{L} b_{}edziemy nazywali mimimalnym automatem deterministycznym rozpoznaj _{}acym j_{}ezyk L, lub krótko: automatem minimalnym dla j_{}ezyka L.

W nast_{}epuj _{}acym przykładzie wykażemy, że eksponencjalne oszacowanie na wzrost liczby stanów przy determinizacji automatu niedeterministycznego (Twierdzenie 1) jest w ogólności optymalne.

Przykład 3 Niech Σ = {0, 1} i niech k ≥ 1. Niech L_{k} b_{}edzie zbiorem słów, które na k-tej od końca pozycji maj _{}a 1, tzn.

L_{k} = {w : |w| ≥ k i w_{|w|+1−k} = 1}

Nietrudno podać automat niedeterministyczny o k + 1 stanach rozpoznaj _{}acy j_{}ezyk L_{k}; pozostawiamy to jako ćwiczenie. Dla określenia liczby stanów minimalnego automatu deterministycznego, rozważmy relacj_{}e ∼_{L_{k}}. Zauważmy najpierw, że żadne dwa różne słowa o długości k nie s _{}a równoważne. Istotnie, jeśli |w| = |u| = k i np. w_{k−i} = 0 a u_{k−i} = 1, to u0^{i} ∈ L_{k}, podczas gdy w0^{i} ∉ L_{k}. Z drugiej strony, nietrudno sprawdzić, że każde słowo jest równoważne, w sensie relacji ∼_{L_{k}}, pewnemu słowu długości k: gdy |w| > k, to w jest równoważne swojemu sufiksowi długości k, a gdy 0 ≤ |w| < k, to w ∼_{L_{k}} 0^{k−|w|}w. A zatem, indeks relacji ∼_{L_{k}} ergo liczba stanów automatu minimalnego jest 2^{k}.

Pytanie. Co powyższy przykład mówi nam na temat operacji lustrzanego odbicia?

1.4 Algorytm minimalizacji automatu deterministycznego

W poprzednim punkcie opisaliśmy, jak z dowolnego automatu deterministycznego rozpoznaj _{}acego j_{}ezyk L można otrzymać automat minimalny A^{L}. Algorytmicznie, problem sprowadza si_{}e do dwóch zadań: eliminacji stanów nieosi _{}agalnych i obliczenia relacji ∼. Kiedy już znamy relacj_{}e ∼, konstrukcja automatu ilorazowego jest bezpośrednia.

Algorytm dla obliczenia stanów osi _{}agalnych już rozważaliśmy w Odcinku 1 (Punkt 2.5, Algorytm 3). Obecnie podamy algorytm obliczania relacji ∼.

Niech wi_{}ec A = (Σ, Q, q_{I}, δ, F) b_{}edzie automatem deterministycznym i L = L(A). W zwi _{}azku z uwag _{}a powyżej, możemy zakładać, że wszystkie stany automatu A s _{}a osi _{}agalne.

Naszym zadaniem jest wyznaczenie relacji ∼⊆ Q × Q, która, jak pami_{}etamy, była zdefiniowana nast_{}epuj _{}aco:

q ∼ q′ ⇔ L(A, q) = L(A, q′)

W rzeczywistości, wyznaczymy uzupełnienie relacji ∼, tj. zbiór par {(q, q′) : q ≁ q′}. W tym celu określimy najpierw pewien graf zorientowany, G_{A}. Wierzchołkami b_{}ed _{}a wszystkie pary nieuporz _{}adkowane {p, q}, p ≠ q. Dalej, prowadzimy kraw_{}edź z wierzchołka

{p, q} do {p′, q′}, o ile {p, q} ≠ {p′, q′} i istnieje σ ∈ Σ t.że p →^{σ} p′ i q →^{σ} q′. (Zauważmy

w tym miejscu, że, z powodu determinizmu automatu A, z każdego wierzchołka grafu G_{A} wychodzi |Σ| kraw_{}edzi. Zatem liczba kraw_{}edzi grafu G_{A} jest O(n^{2}).) W grafie G_{A} zaznaczamy najpierw wszystkie wierzchołki postaci {p, q}, takie że p ∈ F i q ∉ F. Zauważmy, że, dla każdej zaznaczonej pary {p, q}, zachodzi na pewno p ≁ q. Niech Z b_{}edzie zbiorem wszystkich zaznaczonych wierzchołków. Twierdzimy, że

Dla każdych p, q ∈ Q, p ≁ q wtedy i tylko wtedy, gdy istnieje ścieżka z wierzchołka {p, q} do jakiegoś wierzchołka w zbiorze Z.

Istotnie, jeśli p ≁ q, to mamy jakieś słowo v = v_{1} … v_{m}, takie, że, np. δ̂(p, v) ∈ F a δ̂(q, v) ∉ F. Mamy wi_{}ec

p →^{v_{1}} p_{1} →^{v_{2}} p_{2} … p_{m−1} →^{v_{m}} p_{m} ∈ F

i

q →^{v_{1}} q_{1} →^{v_{2}} q_{2} … q_{m−1} →^{v_{m}} q_{m} ∉ F

Nietrudno widzieć, że

{p, q} → {p_{1}, q_{1}} → … {p_{m−1}, q_{m−1}} → {p_{m}, q_{m}}

jest wówczas ż _{}adan _{}a ścieżk _{}a w grafie, przy czym p_{m} ∈ F a q_{m} ∉ F, a wi_{}ec wierzchołek {p_{m}, q_{m}} należy do Z.

Dla udowodnienia implikacji odwrotnej, zauważmy najpierw, że jeśli p ≁ q i istnieje strzałka z {p′, q′} do {p, q}, to również p′ ≁ q′. Zatem teza powyższa wynika łatwo przez indukcj_{}e ze wzgl_{}edu na długość ścieżki, jaka prowadzi z wierzchołka {p, q} do zbioru Z.

Wyznaczenie relacji ≁ sprowadza si_{}e wi_{}ec do obliczenia zbioru wierzchołków grafu G_{A}, dla których istnieje ścieżka prowadz _{}aca do jakiegoś wierzchołka w zbiorze Z. Łatwo widzieć, że interesuj _{}acy nas zbiór jest zbiorem wierzchołków osi _{}agalnych z Z w grafie dualnym G_{A}^{d} (tj., jeśli odwrócimy kierunek każdej kraw_{}edzi). Możemy wi_{}ec dla jego obliczenia zastosować Algorytm 3 z Odcinka 1 (dokładniej, graf G_{A}^{d}, w którym kraw_{}edzie nie s _{}a etykietowane, możemy traktować jak graf automatu nad jednoliterowym alfabetem). Czas działania tego algorytmu jest proporcjonalny do liczby kraw_{}edzi w grafie, która w wypadku grafu G_{A} jest O(n^{2}), takie jest też wi_{}ec oszacowanie czasu działania przedstawionego algorytmu. Algorytm ten znany jest jako Algorytm Moore’a.

Nietrudno pokazać, że również wyznaczenie grafu G_{A} i zbioru Z może być wykonane w czasie O(n^{2}), co pozwala nam podsumować powyższe rozważania w nast_{}epuj _{}acym twierdzeniu.

Twierdzenie 5 (Algorytm Moore’a) Istnieje algorytm, który dla danego automatu deterministycznego o n stanach konstruuje w czasie O(n^{2}) minimalny automat deterministyczny rozpoznaj _{}acy ten sam j_{}ezyk.

W ćwiczeniach przedstawimy Algorytm Hopcrofta, którego czas działania jest lepszy, mianowicie O(n log n).

Zauważmy jeszcze na koniec, że ł _{}acz _{}ac opisany wyżej algorytm z algorytmem otrzymywania automatu niedeterministycznego z wyrażenia regularnego i algorytmem determinizacji automatu niedeterministycznego, otrzymujemy metod_{}e konstrukcji automatu minimalnego dla j_{}ezyka zadanego wyrażeniem regularnym. Metoda ta nie jest jednak w każdym przypadku efektywna z uwagi na eksponencjalny wzrost rozmiaru automatu w procesie determinizacji.

Zagadnienie efektywnej metody znajdywania automatu niedeterministycznego o najmniejszej możliwej liczbie stanów, jest problemem otwartym.

ćwiczenia

Algorytm Hopcrofta

Przedstawimy teraz inny algorytm minimalizacji automatu. Niech A = (Σ, Q, q_{I}, δ, F) b_{}edzie, jak wyżej, automatem deterministycznym. Tym razem b_{}edziemy d _{}ażyć do obliczenia relacji ∼ (zdefiniowanej ja wyżej) poprzez obliczenie podziału, jaki ta relacja równoważności wyznacza na zbiorze Q. Poszukiwany podział b_{}edzie znaleziony “metod _{}a kolejnych przybliżeń”, przy czym każdy kolejny podział b_{}edzie rozdrobnieniem poprzedniego.

Niech X, Y ⊆ Q, a ∈ Σ. Określamy X′ = {q ∈ X : δ(q, a) ∈ Y }, X′′ = {q ∈ X : δ(q, a) ∉ Y }. Oczywiście, X′ ∪ X′′ = X, X′ ∩ X′′ = ∅. Jeżeli oba zbiory X′, X′′ s _{}a niepuste, to powiemy, że para (Y, a) łamie zbiór X, a par_{}e {X′, X′′} nazwiemy złamaniem zbioru X przez (Y, a). Jeżeli P jest podziałem zbioru Q, to złamaniem P przez (Y, a) nazywamy podział otrzymany z podziału P przez zast _{}apienie każdego X ∈ P, który jest łamany przez (Y, a), przez jego złamanie X′, X′′.

W algorytmie b_{}edziemy używać dwóch typów struktur: z jednej strony, podziału (zmienna P), a z drugiej, listy par (Y, a) przeznaczonych do łamania (zmienna L). Przyjmujemy oznaczenie X̄ = Q − X.

procedura Hopcroft P := {F, F̄}; jeśli |F | < |F̄| to L := ((F, σ) : σ ∈ Σ) w przeciwnym przypadku L := ((F̄, σ) : σ ∈ Σ) dopóki L ≠ ∅ wykonuj

1. zdejmij par_{}e (Y, a) z listy L;

2. oblicz zbiór B tych X ∈ P, że para (Y, a) łamie X;

3. dla X ∈ B, b ∈ Σ wykonuj

(a) oblicz złamanie {X′, X′′} przez (Y, a);

(b) jeśli (X, b) ∈ L to zast _{}ap (X, b) w L przez (X′, b), (X′′, b);

(c) w przeciwnym przypadku jeśli |X′| < |X′′| to doł _{}acz (X′, b) do L w przeciwnym przypadku doł _{}acz (X′′, b) do L

Należy dowieść, że algorytm działa poprawnie, tzn. zawsze zatrzymuje si_{}e i końcow _{}a wartości _{}a zmiennej P jest podział wyznaczony przez relacj_{}e ∼ z wykładu. Ponadto, należy wykazać, że czas działania algorytmu jest O(n log n).

2 Własności domkni_{}ecia klasy j_{}ezyków regularnych

Rodzina j_{}ezyków regularnych ma wiele dobrych własności, w szczególności jest zamkni_{}eta na wi_{}ekszość możliwych do pomyślenia operacji. W poniższym twierdzeniu podsumowujemy te własności. Poszczególne punkty zostały już udowodnione w trakcie wykładu lub jako ćwiczenia.

Twierdzenie 6 Klasa j_{}ezyków regularnych jest zamkni_{}eta na

• operacje Boole’owskie, tzn. jeżeli L, M ⊆ Σ^{∗} s _{}a j_{}ezykami regularnymi, to również L ∪ M, L ∩ M, Σ^{∗} − L, L − M, s _{}a j_{}ezykami regularnymi;

• konkatenacj_{}e, tzn. jeżeli L, M ⊆ Σ^{∗} s _{}a j_{}ezykami regularnymi, to również LM jest j_{}ezykiem regularnym;

• operacj_{}e gwiazdki, tzn. jeżeli L jest j_{}ezykiem regularnym, to L^{∗} jest również j_{}ezykiem regularnym;

• ilorazy przez dowolne zbiory, tzn. jeżeli L jest j_{}ezykiem regularnym i X ⊆ Σ^{∗} jest dowolnym j_{}ezykiem, to X^{−1}L i LX^{−1} s _{}a j_{}ezykami regularnymi;

• operacj_{}e lustrzanego odbicia, tzn. jeżeli L jest j_{}ezykiem regularnym, to L^{R} = {w^{R} : w ∈ L} jest j_{}ezykiem regularnym;

• podstawienie, tzn. jeśli f : Σ → P (Γ^{∗}) jest funkcj _{}a tak _{}a, że, dla każdego σ ∈ Σ, f(σ) jest j_{}ezykiem regularnym i L ⊆ Σ^{∗} jest j_{}ezykiem regularnym, to f̂(L) jest również j_{}ezykiem regularnym; • obrazy homomorficzne, tzn. jeśli L ⊆ Σ^{∗} jest j_{}ezykiem regularnym, i h : Σ → Γ^{∗} jest

homomorfizmem, to h(L) jest j_{}ezykiem regularnym;

• przeciwobrazy homomorficzne, tzn. jeśli M ⊆ Γ^{∗} jest j_{}ezykiem regularnym, i h : Σ → Γ^{∗} jest homomorfizmem, to h^{−1}(M) jest j_{}ezykiem regularnym.

Wi_{}ekszość powyższych własności domkni_{}ecia ma charakter efektywny, tzn. maj _{}ac dane automaty lub wyrażenia regularne dla j_{}ezyków L, M, …, potrafimy znaleźć automat (wyrażenie) dla j_{}ezyka otrzymanego w wyniku stosowanej operacji. Nie dotyczy to jedynie operacji ilorazu przez dowolny zbiór, który nie musi być zadany efektywnie, jeśli jednak ograniczymy si_{}e do ilorazów przez j_{}ezyki regularne, to operacja jest, oczywiście, efektywna.

Własności te pozwalaj _{}a wi_{}ec na dość elastyczne konstruowanie j_{}ezyków regularnych. Z drugiej strony mog _{}a też być przydatne przy dowodzie nieregularności jakiegoś j_{}ezyka. Rozważmy np. j_{}ezyk bb^{∗}{a^{n}b^{n} : n ∈ N}. J_{}ezyk ten nie jest regularny, choć spełnia tez_{}e lematu o pompowaniu (przynajmniej w tej formie jak _{}a przyj_{}eliśmy w Lemacie 4 w Odcinku 1). Jednakże stosuj _{}ac lewostronny iloraz przez bb^{∗} otrzymujemy j_{}ezyk {a^{n}b^{n} : n ∈ N}, którego nieregularność potrafimy wykazać. St _{}ad, z własności domkni_{}ecia na ilorazy, możemy wnioskować o nieregularności pierwszego j_{}ezyka.

Zadania o j_{}ezykach regularnych

1. Dowieść, że jeśli L jest j_{}ezykiem regularnym, to zbiór prefiksów słów z L, zbiór sufiksów słów z L, a także zbiór podsłów, tzn.

{w : (∃u, v ∈ Σ^{∗})uwv ∈ L}

s _{}a j_{}ezykami regularnymi.

2. Skonstruować minimalny automat deterministyczny rozpoznaja̧cy jȩzyk L ⊆ {a, b}^{∗}, gdzie

• L = {ϵ} ,

• L = {a, b, aba} ,

• L jest zbiorem słów w których a wystȩpuje dokładnie 1993 razy,

• L jest zbiorem słów w których liczba wyst _{}apień a daje reszt_{}e 3 z dzielenia przez 5.

3. Ile stanów ma minimalny automat deterministyczny rozpoznaj _{}acy, że ci _{}ag zer i jedynek jest rozwini_{}eciem binarnym liczby podzielnej przez 3?

4. W hotelu jest K pi_{}eter. Przejazd windy bez zatrzymania z pi_{}etra i na pi_{}etro j (i ≠ j) uważamy za jednostkow _{}a akcj_{}e. Z każd _{}a tak _{}a akcj _{}a wi _{}ażemy liter_{}e: G jeśli i < j, D jeśli i > j. Rozważamy możliwe trasy windy, które rozpoczynaj _{}a si_{}e i kończ _{}a na parterze. Każda taka trasa wyznacza słowo nad alfabetem {G, D}. Niech L ⊆ {G, D}^{∗} b_{}edzie zbiorem wszystkich tak otrzymanych słów.

(a) Dowieść, że L jest regularny.

(b) Ile stanów ma minimalny automat deterministyczny rozpoznaj _{}acy L?

5. Niech L = {a^{2^{n}} : n ≥ 1}. Dowieść , że jedyne podzbiory L bȩda̧ce jȩzykami regularnymi, to zbiory skończone.

6. Σ jest dowolnym alfabetem. Ustalamy słowo w ∈ Σ^{∗} o długości n. Skonstruować automat deterministyczny o n + 1 stanach rozpoznaj _{}acy wszystkie słowa u ∈ Σ^{∗} zawieraj _{}ace w jako podsłowo (tzn. u = v_{1}wv_{2}; mówi _{}ac bardziej obrazowo, konstruowany automat poszukuje wzorca w w tekście u).

7. Niech L b_{}edzie zbiorem słów w ∈ {a, b}^{∗}, które zawieraj _{}a przynajminiej jedno wyst _{}apienie symbolu b, przy czym bezpośrednio przed ostatnim wyst _{}apieniem symbolu b w słowie w musi wyst _{}apić symbol a. Dowieść, że L jest j_{}ezykiem regularnym. Podać liczb_{}e stanów minimalnego automatu deterministycznego rozpoznaj _{}acego j_{}ezyk L. Skonstruować wyrażenia regularne opisuj _{}ace każd _{}a z klas abstrakcji relacji ∼_{L} z twierdzenia Myhill’a–Nerode’a wyznaczonej przez L.

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

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

10. (*) Dowieść, że dla dowolnego j_{}ezyka regularnego L, j_{}ezyk

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

jest również regularny.

Rozwi _{}azania niektórych zadań

Rozwi _{}azanie zadania 9.

Niech L b_{}edzie opisanym j_{}ezykiem. Rozważmy relacj_{}e ∼_{L} z twierdzenia Myhill’a Nerode’a. Twierdzimy, że każde słowo jest równoważne pewnemu słowu długości 7. Istotnie, zauważmy najpierw, że wszystkie słowa w ∉ L s _{}a równoważne mi_{}edzy sob _{}a, a wi_{}ec równoważne w szczególności słowu 1111111. Dalej, nietrudno widzieć, że każde słowo, które należy do L i jest dłuższe niż 7, jest równoważne swojemu sufiksowi długości 7. Natomiast słowo w o długości |w| = i < 7 jest równoważne słowu 0^{7−i}w. A zatem relacja ∼_{L} ma nie wi_{}ecej niż 2^{7} klas abstrakcji, j_{}ezyk L jest wi_{}ec regularny.

Powyższy argument prowadzi też w prosty sposób do wyznaczenia automatu, którego stanami s _{}a słowa zero-jedynkowe długości 7, a którego przejścia s _{}a postaci

a_{1}a_{2} … a_{7}, i → a_{2}a_{3} … a_{7}i

gdzie i ∈ {0, 1}, o ile ci _{}ag a_{1}a_{2} … a_{7} zawiera nie wi_{}ecej niż 4 jedynki, w przeciwnym razie odpowiednie przejście jest

a_{1}a_{2} … a_{7}, i → a_{1}a_{2} … a_{7}

dla i = 0, 1. Stanem pocz _{}atkowym jest ci _{}ag 0000000, a stanami akceptuj _{}acymi s _{}a oczywiście te ci _{}agi, które zawieraj _{}a nie wi_{}ecej niż 4 jedynki.

Nie jest to jednak automat minimalny.

Poniżej wyznaczymy liczb_{}e klas abstrakcji relacji ∼_{L}, konstrukcja samego automatu wynika z twierdzenia Myhill’a-Nerode’a. Na mocy wcześniejszej uwagi, wystarczy odpowiedzieć na pytanie, które słowa długości 7 s _{}a równoważne.

Słowo w ∈ {0, 1}^{7} nazwiemy pełnym, jeśli zawiera dokładnie 4 jedynki.

Lemat 1. Dwa różne słowa pełne s _{}a nierównoważne.

Istotnie, niech w = w_{1} … w_{7}, v = v_{1} … v_{7} b_{}ed _{}a pełnymi słowami i niech i b_{}edzie najwyższ _{}a pozycj _{}a, gdzie słowa w i v si_{}e różni _{}a, powiedzmy w_{i} = 0 i v_{i} = 1. Niech k b_{}edzie liczb _{}a jedynek leż _{}acych w słowie w na lewo od pozycji i,

k = |{j : j < i ∧ w_{j} = 1}|

Zauważmy, że k ≥ 1, bo w przeciwnym razie w miałoby mniej jedynek niż v, oraz, że, oczywiście, k < i (w szczegolności wi_{}ec i > 1). Niech u = 0^{j}1^{k}, gdzie j + k = i − 1 (j ≥ 0). Twierdzimy, że wu ∈ L, podczas gdy vu ∉ L. Ten ostatni fakt wynika łatwo z konstrukcji, gdyż słowo v_{i} … v_{7}u jest długości 7 i zawiera 5 jedynek. Dla sprawdzenia, że wu ∈ L, wystarczy sprawdzić wszystkie podsłowa długości 7 postaci w_{m} … w_{7}0^{j}1^{ℓ}, gdzie m < i i ℓ > 0 (pozostałe podsłowa długości 7 słowa wu nie mog _{}a zawierać wi_{}ecej jedynek niż w).

k = 3, ℓ = 1

Zauważmy jednak, że i − m = k − ℓ (rysunek), a zatem słowo w_{m}w_{m+1} … w_{i−1} zawiera co najwyżej k − ℓ jedynek, podczas gdy słowo w_{i}w_{i+1} … w_{7}0^{j} zawiera 7 − k jedynek, całe słowo w_{m} … w_{7}0^{j}1^{ℓ} zawiera wi_{}ec niewi_{}ecej niż (k − ℓ) + (7 − k) + ℓ = 7 jedynek. Słowa w i v nie s _{}a zatem równoważne, co kończy dowód Lematu 1.

Lemat 2. Każde słowo w ∈ {0, 1}^{7} zawieraj _{}ace k < 4 jedynki jest równoważne słowu pełnemu jakie otrzymamy z w pzez zast _{}apienie 4−k najwcześniej wyst_{}epuj _{}acych zer przez jedynki.

Np., 0100100 jest równoważne 1110100. Istotnie, niech w b_{}edzie słowem w którym wyst_{}epuj _{}a k < 4 jedynki i niech v b_{}edzie słowem otrzymanym z w jak w lemacie. Oczywiście, (∀u)vu ∈ L ⇒ wu ∈ L. Przypuśćmy, że dla pewnego u implikacja odwrotna nie zachodzi, tj. wu ∈ L, ale vu ∉ L. Wówczas możemy znaleźć i, takie że v_{i}v_{i+1} … v_{7}u_{1} … u_{i−1} jest podsłowem vu długości 7 zawieraj _{}acym wi_{}ecej niż 4 jedynki. Wybierzmy najmniejsze i o tej własności. Pami_{}etajmy, że odpowiednie słowo w_{i}w_{i+1} … w_{7}u_{1} … u_{i−1} zawiera nie wi_{}ecej niż 4 jedynki. Zatem v_{i}v_{i+1} … v_{7} różni si_{}e od w_{i}w_{i+1} … w_{7}, tzn. dla pewnego i ≤ i_{0}, w_{i_{0}} = 0 a v_{i_{0}} = 1. Twierdzimy dalej, że v_{i−1} = 1. Istotnie, gdyby v_{i−1} = 0, to także w_{i−1} = 0 i zgodnie z definicj _{}a v, na pozycji i − 1 w słowie w zero powinno zostać zast _{}apione przez 1 (wiemy, że po transformacji w_{1} … w_{i−2} w v_{1} … v_{i−2} pozostawało jeszcze jakieś zero do zast _{}apienia, skoro zero na pozycji i_{0} ≥ i zostało zast _{}apione przez 1 !). A zatem v_{i−1} = 1. Wówczas jednak słowo 3 v_{i−1}v_{i} … v_{7}u_{1} … u_{i−2} zawiera co najmniej tyle samo jedynek, co rozważane wcześniej słowo v_{i}v_{i+1} … v_{7}u_{1} … u_{i−1}, co przeczy minimalności i. Ta uwaga kończy dowód Lematu 2.

Pami_{}etaj _{}ac o tym, że wszystkie słowa nie należ _{}ace do L s _{}a równoważne, oraz że każde słowo jest równoważne pewnemu słowu o długości 7, z Lematów 1 i 2, otrzymujemy liczb_{}e klas abstrakcji relacji ∼_{L}, która stanowi zarazem liczb_{}e stanów minimalnego automatu deterministycznego

( \begin{matrix}7 \\ 4 \end{matrix} ) + 1 = 36

Uwaga. Powyższa liczba może być otrzymana jeszcze na kilka innych sposobów. Na przykład, nietrudno zauważyć, że każde dwa słowa długości 7 zakończone sufiksem 000 s _{}a równoważne. Obserwacja ta może być uogólniona przez ci _{}ag nast_{}epuj _{}acych stwierdzeń: każde dwa słowa długości 7 zakończone sufiksem długości 4 zawieraj _{}acym dokładnie jedn _{}a jedynk_{}e, s _{}a równoważne, podobnie każde dwa słowa zakończone sufiksem długości 5 zawieraj _{}acym dokładnie dwie jedynki, itd. (ostatnie stwierdzenie dotyczy sufiksów tożsamych z całym słowem i jest trywialne). Powyższe uwagi prowadz _{}a do wyznaczenia liczby nierównoważnych słów długości 7, które należ _{}a do L:

( \begin{matrix}3 \\ 0 \end{matrix} )+(( \begin{matrix}4 \\ 1 \end{matrix} ) − ( \begin{matrix}0 \\ 0 \end{matrix} ))+(( \begin{matrix}5 \\ 2 \end{matrix} ) − ( \begin{matrix}4 \\ 1 \end{matrix} ))+(( \begin{matrix}6 \\ 3 \end{matrix} ) − ( \begin{matrix}5 \\ 2 \end{matrix} ))+(( \begin{matrix}7 \\ 4 \end{matrix} ) − ( \begin{matrix}6 \\ 3 \end{matrix} )) = ( \begin{matrix}7 \\ 4 \end{matrix} )

3Gdy i − 2 = 0, rozumiemy przez to, że sufiks u_{1} … u_{i−2} jest pusty.

Rozwi _{}azanie zadania 10. Niech A = (Σ, Q, q_{1}, δ, F) b_{}edzie deterministycznym automatem, takim że L(A) = L. Niech Q = {q_{1}, …, q_{n}}. W dalszym ci _{}agu rozważań b_{}edziemy dla wygody notacyjnej utożsamiać funkcj_{}e f : Q → Q z ci _{}agiem (f(q_{1}), …, f(q_{n})). Rozpocznijmy od uwagi, że każde słowo w ∈ Σ^{∗} wyznacza funkcj_{}e f_{w} : Q → Q określon _{}a

f_{w} = (δ̂(q_{1}, w), …, δ̂(q_{n}, w))

Skonstruujemy najpierw automat A′, który, dla każdego w, “oblicza” funkcj_{}e f_{w} w nast_{}epuj _{}acym sensie. Zbiorem stanów automatu A′ jest właśnie Q^{Q} (zbiór funkcji z Q w Q), stanem pocz _{}atkowym jest funkcja identycznościowa id = (q_{1}, …, q_{n}), a funkcja przejścia δ′ jest określona przez

δ′((p_{1}, …, p_{n}), σ)(q) = (δ(p_{1}, σ), …, δ(p_{n}, σ))

Nietrudno wykazać przez indukcj_{}e, że dla dowolnego w

δ̂′(id, w) = f_{w}

w tym właśnie sensie automat A′ “oblicza” funkcj_{}e f_{w} (ewentualne stany akceptuj _{}ace nie maj _{}a tu znaczenia).

Przypuśćmy na chwil_{}e, że dla pewnego w znamy funkcj_{}e f = f_{w}. Możemy wówczas skonstruować automat, powiedzmy A_{f}, który czytaj _{}ac słowo w potrafi “obliczyć” stan, do którego automat A dochodzi po przeczytaniu słowa w^{|w|}. Zbiór stanów automatu A_{f} pokrywa si_{}e ze zbiorem stanów automatu A, stanem pocz _{}atkowym jest q_{1}, a funkcja przejścia, powiedzmy δ′′, jest określona przez

δ′′(q, σ) = f(q)

Nietrudno widzieć, że istotnie

δ̂′′(q_{1}, w) = δ̂(q_{1}, w^{|w|})

Oczywiście, automat skończony nie może “z góry” znać funkcji f_{w}. Jednakże, korzystaj _{}ac z faktu, że możliwych funkcji f_{w} jest skończenie wiele, możemy zastosować produkt automatów A_{f} po wszystkich możliwych funkcjach f, jednocześnie obliczaj _{}ac “właściw _{}a” funkcj_{}e f_{w} przy pomocy automatu A′. Po przeczytaniu słowa w pozostaje sprawdzić, czy na współrz_{}ednej automatu produktowego odpowiadaj _{}acej obliczonej funkcji f_{w} pojawił si_{}e stan akceptuj _{}acy.

Poniżej podamy formaln _{}a konstrukcj_{}e automatu B, takiego że

L(B) = {w : w^{|w|} ∈ L}

Ustawmy zbiór Q^{Q} w ci _{}ag: Q^{Q} = {g_{1}, …, g_{n^{n}}} (pami_{}etamy n = |Q|). Określamy

• zbiór stanów automatu B: Q^{n+n^{n}},

• stan pocz _{}atkowy: (q_{1}, q_{1}, …, q_{1}),

• funkcja przejścia:

(p_{1}, …, p_{n}, s_{1}, …, s_{n^{n}}), σ → (δ(p_{1}, σ), …, δ(p_{n}, σ), g_{1}(s_{1}), …, g_{n^{n}}(s_{n^{n}}))

• stany akceptuj _{}ace:

{(p_{1}, …, p_{n}, s_{1}, …, s_{n^{n}}) : (p_{1}, …, p_{n}) = g_{j} ∧ s_{j} ∈ F dla pewngo 1 ≤ j ≤ n^{n}}

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.