Jȩzyki, Automaty i Obliczenia. Odcinek 3

Gramatyki bezkontekstowe

Damian Niwiński

Październik 2003

1 Gramatyki i wyprowadzenia

Gramatyka bezkontekstowa może być przedstawiona jako nast_{}epuj _{}acy układ

G = (Σ, V, X_{I}, R)

gdzie

• Σ jest skończonym zbiorem symboli, który nazywamy alfabetem gramatyki, elementy tego zbioru nazywamy też symbolami końcowymi gramatyki;

• V jest skończonym zbiorem symboli rozł _{}acznym z Σ; jego elementy nazywamy symbolami niekońcowymi albo zmiennymi gramatyki;

• X_{I} ∈ V jest symbolem startowym gramatyki;

• R jest skończonym zbiorem reguł przepisywania (krótko: reguł), R ⊆ V × (Σ ∪ V)^{∗}.

Zgodnie z definicj _{}a, każda reguła jest par _{}a postaci (X, w), dla pewnej zmiennej X ∈ V i słowa w ∈ (Σ ∪ V)^{∗}; mówimy że jest to reguła przepisywania zmiennej X. Fakt, że (X, w) ∈ R, b_{}edziemy także zapisywać X →^{G} w. Jeżeli {(X, w_{1}), …, (X, w_{k})}, s _{}a wszystkimi regułami przepisywania zmiennej X, to b_{}edziemy je zapisywać w notacji skróconej, tzw. notacji Backusa-Naura,

X → w_{1}|w_{2}| … |w_{k}

Relacj_{}e R rozszerzymy do relacji →^{G}⊆ (Σ ∪ V)^{∗} × (Σ ∪ V)^{∗} określonej nast_{}epuj _{}aco

w →^{G} v ⇔ (∃(X, u) ∈ R) (∃α, β ∈ (Σ ∪ V)^{∗}) w = αXβ ∧ v = αuβ

Mówi _{}ac intuicyjnie, relacja w →^{G} v zachodzi, kiedy słowo v może być otrzymane przez jednokrotne zastosowanie reguły (X, u) do pewnego wyst _{}apienia zmiennej X w słowie w.

Zauważmy, że gdy X jest zmienn _{}a, to wprowadzona wyżej notacja X →^{G} w na oznaczenie reguły przepisywania zmiennej X jest niesprzeczna z definicj _{}a relacji →^{G}, gdyż

X →^{G} w ⇔ (X, w) ∈ R.

Każdy ci _{}ag w_{0}, w_{1}, …, w_{k−1}, w_{k}, gdzie 0 ≤ k, w_{0} = w, w_{k} = v, a ponadto w_{i} →^{G} w_{i+1}

dla i = 0, …, k − 1, nazywamy wyprowadzeniem słowa v ze słowa w w gramatyce G. Określamy relacj_{}e w →^{G∗} v przez

w →^{G∗} v ⟺ istnieje wyprowadzenie v z w

Nietrudno jest wykazać, że relacja →^{G∗} jest zwrotno–przechodnim domkni_{}eciem relacji →^{G}, tj. najmniejsz _{}a relacj _{}a zwrotn _{}a i przechodni _{}a zawieraj _{}ac _{}a →^{G}. Mówimy, że słowo w ∈ Σ^{∗} jest wyprowadzalne ze zmiennej X w gramatyce G, jeśli X →^{G∗} w. Przyjmujemy oznaczenie

L(G, X) = {w ∈ Σ^{∗} : X →^{G∗} w}

Jeśli słowo w ∈ Σ^{∗} jest wyprowadzalne z symbolu startowego gramatyki, to mówimy krótko, że słowo w jest wyprowadzalne w gramatyce G, a zbiór wszystkich takich słów określamy jako j_{}ezyk wyprowadzalny w gramatyce G lub generowany przez gramatyk_{}e G, który oznaczamy L(G). Mamy wi_{}ec

L(G) = L(G, X_{I}) = {w ∈ Σ^{∗} : X_{I} →^{G∗} w}

W dalszym ci _{}agu, jeżeli gramatyka G b_{}edzie znana z kontekstu, b_{}edziemy cz_{}esto opuszczali górny indeks G, pisz _{}ac po prostu w → v lub w →^{∗} v.

Przykład 1 (a) Nast_{}epuj _{}aca gramatyka nad alfabetem {(,), [,]} generuje poprawnie zbudowane ci _{}agi nawiasów

X → ϵ | XX | (X) | [X]

(b) Nast_{}epuj _{}aca gramatyka nad alfabetem {(,), +, ∗, 0, 1} generuje poprawnie zbudowane wyrażenia arytmetyczne

X → 0 | 1 | X + X | X ∗ X | (X)

1.1 Wyprowadzenia lewostronne

Określamy relacj_{}e →^{lG} stanowi _{}ac _{}a podzbior relacji →^{G},

w →^{lG} v ⇔ (∃(X, u) ∈ R) (∃α ∈ Σ^{∗})(∃β ∈ (Σ ∪ V)^{∗})w = αXβ ∧ v = αuβ

Mówi _{}ac intuicyjnie, słowo v zostało otrzymane ze słowa w podobnie jak w relacji w →^{G} v, ale wyst _{}apienie zmiennej X do jakiego została zastosowana reguła przepisywania X →^{G} u było najbardziej na lewo wysuni_{}etym (ang. left-most) wyst _{}apieniem jakiegokolwiek symbolu niekońcowego w słowie w. Ci _{}ag w = w_{0}, w_{1}, …, w_{k−1}, w_{k} = v, 0 ≤ k, t. że w_{i} →^{lG} w_{i+1}, dla i = 0, …, k − 1, nazywamy wyprowadzeniem lewostronnym (ang. leftmost derivation) słowa v ze słowa w. Zwrotno-przechodnie domkni_{}ecie relacji →^{lG} b_{}edziemy oznaczać →^{lG∗}.

1.2 Drzewa wyprowadzeń

Struktura drzewa jest spotykana w informatyce we wielu kontekstach, przy czym używanych jest kilka nierównoważnych modeli matematycznych tego poj_{}ecia. Na przyklad, jeśli zdefiniujemy drzewo jako spójny graf, w którym liczba wierzchołków jest o 1 wi_{}eksza od liczby kraw_{}edzi, to pominiemy taki aspekt drzewa jak wyróżnienie pewnego wierzchołka jako korzenia oraz uporz _{}adkowanie nast_{}epników danego wierzchołka “od lewej do prawej”. Dogodnym modelem uwzgl_{}edniaj _{}acym oba te aspekty jest przedstawienie drzewa jako pewnego zbioru słów, lub, w przypadku drzewa etykietowanego, funkcji ze zbioru słów w zbiór etykiet. Idea jest tu bardzo prosta: w drzewie, powiedzmy, binarnym, można utożsamić wierzchołek ze ścieżk _{}a jak _{}a można do niego dojść od korzenia, tzn. ci _{}agiem wyboru kierunków, np. lewo, prawo, prawo . W ogólniejszym przypadku, za zbiór kierunków możemy przyj _{}ać dowolny segment pocz _{}atkowy zbioru liczb naturalnych.

Zbiór liczb naturalnych oznaczamy ω. Zgodnie z nasz _{}a konwencj _{}a, ω^{∗} oznacza zbiór słów nad ω, a wi_{}ec skończonych ci _{}agów o wyrazach naturalnych. Jeśli v ∈ ω^{∗}, to każdy ci _{}ag vi, i ∈ ω, nazywamy nast_{}epnikiem ci _{}agu v. Jeśli I ⊆ ω^{∗} i v ∈ I, to przez succ(I, v) oznaczamy zbiór tych nast_{}epników ci _{}agu v, które należ _{}a do I. Niepusty skończony zbiór T ⊆ ω^{∗} nazywamy drzewem (nieetykietowanym), jeśli spełnione s _{}a nast_{}epuj _{}ace warunki

• T jest zamkni_{}ety na prefiksy (tzn. (w ∈ T ∧ v ≤ w) ⇒ v ∈ T)

• dla każdego v ∈ T, istnieje k ∈ ω (zależne od v), takie, że succ (T, v) = {v1, …, vk} (jeśli k = 0, to succ(T, v) = ∅).

Elementy drzewa T nazywamy wierzchołkami, słowo ϵ (które oczywiście znajduje si_{}e w każdym drzewie) nazywamy korzeniem, a wierzchołki v, dla których succ(T, v) = ∅, nazywamy liśćmi drzewa T. Zauważmy, że relacja “być prefiksem”cz_{}eściowo porz _{}adkuje zbiór wierzchołków drzewa^{1}. Liczb_{}e

depth(T) = max{|w| : w ∈ dom(T)}

nazywamy gł_{}ebokości _{}a drzewa T.

Jeśli E jest dowolnym zbiorem, a T jest drzewem, to każd _{}a funkcj_{}e t : T → E nazywamy drzewem etykietowanym zbiorem etykiet E. Zbiór T nazywamy wówczas dziedzin _{}a drzewa t i oznaczamy dom(t) (z angielskiego domain = dziedzina). Poj_{}ecia “korzeń”, “liść” itd. używane w odniesieniu do drzewa etykietowanego, odnosz _{}a si_{}e oczywiście do dom(t).

Jeśli t : dom(t) → E jest drzewem i w ∈ dom(t), to poddrzewem drzewa t wyznaczonym przez wierzchołek w, nazywamy drzewo t.w określone nast_{}epuj _{}aco:

• dom(t.w) = {w}^{−1} dom(t) = {u : wu ∈ dom(t)},

• t.w(u) = t(wu), dla u ∈ dom(t.w).

1Porz _{}adek ten można go rozszerzyć do porz _{}adku liniowego, np. porz _{}adku leksykograficznego na ω^{∗} indukowanego przez standardowy porz _{}adek na ω.

Zdefiniujemy teraz operacj_{}e podstawienia, która, mówi _{}ac intuicyjnie, pozwoli zast_{}epować liście drzewa innymi drzewami. Niech t : dom(t) → E b_{}edzie drzewem etykietowanym i niech v_{1}, …, v_{m} b_{}ed _{}a różnymi liśćmi drzewa t (niekoniecznie wszystkimi). Niech t_{i} : dom(t_{i}) → E, i = 1, …, m, b_{}ed _{}a etykietowanymi drzewami. Określimy drzewo t[v_{1} ← t_{1}, …, v_{m} ← t_{m}], w skróconej notacji t[v⃗ ← t⃗], które stanowi rezultat jednoczesnego podstawienia w drzewie t drzewa t_{i} na wierzchołek v_{i} odpowiednio, dla i = 1, …, m.

• dom(t[v⃗ ← t⃗]) = dom(t) ∪ ⋃_{i=1,...,m} v_{i}dom(t_{i})

• t[v⃗ ← t⃗](w) = t(w), dla w ∈ dom(t) − {v_{1}, …, v_{m}}

• t[v⃗ ← t⃗](v_{i}u) = t_{i}(u), dla każdego u ∈ dom(t_{i}), i = 1, …, m.

Opieraj _{}ac si_{}e na definicji, nie jest trudno sprawdzić, że operacja podstawienia jest ł _{}aczna w nast_{}epuj _{}acym sensie: niech t, r, s b_{}ed _{}a drzewami i niech v ∈ dom(t), u ∈ dom(r). Wówczas:

(t[v ← r])[vu ← s] = t[v ← r[u ← s]]

Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a i niech Y ∈ V. Drzewo D : dom(D) → Σ∪V ∪{ϵ} nazwiemy drzewem wyprowadzenia ze zmiennej Y, jeśli spełnione s _{}a nast_{}epuj _{}ace warunki.

1. D(ϵ) = Y;

2. dla każdego w ∈ dom(D), jeśli D(w) ∈ Σ ∪ {ϵ}, to w jest liściem;

3. dla każdego w ∈ dom(D), jeśli D(w) ∈ V, powiedzmy D(w) = Z, to zachodzi jedna z nast_{}epuj _{}acych możliwości:

(a) w jest liściem;

(b) istnieje reguła Z →^{G} ϵ i w ma dokładnie jeden nast_{}epnik w1, przy czym D(w1) = ϵ; (c) istnieje reguła Z →^{G} c_{1} … c_{k}, gdzie c_{1}, …, c_{k} ∈ Σ ∪ V i w ma dokładnie k

nast_{}epników: w1, …, wk, oraz D(wℓ) = c_{ℓ}, dla ℓ = 1, …, k.

W przypadkach (3b) i (3c) mówimy, że w wierzchołku w została zastosowana reguła Z →^{G} ϵ lub Z →^{G} c_{1} … c_{k}, odpowiednio.

Plonem drzewa wyprowadzenia D nazwiemy słowo α ∈ (Σ∪V)^{∗}, jakie można otrzymać z drzewa składaj _{}ac etykiety wszystkich liści w porz _{}adku “od lewej do prawej”. Bardziej dokładnie, niech v_{1}, …, v_{m} b_{}ed _{}a wszystkimi liśćmi drzewa D w porz _{}adku leksykograficznym^{2}. Określamy słowo y(D) ∈ (Σ ∪ V)^{∗} (z angielskiego yield), nazywane plonem drzewa D,

y(D) = D(v_{1}) … D(v_{m})

Drzewo wyprowadzenia nazwiemy maksymalnym, jeśli nie zachodzi przypadek 3a, tzn. żaden liść nie jest etykietowany zmienn _{}a. Nietrudno jest wykazać, że jeśli D jest maksymalnym drzewem wyprowadzenia, to y(D) ∈ Σ^{∗}.

Zbiór wszystkich drzew wyprowadzenia w gramatyce G ze zmiennej X b_{}edziemy oznaczali przez D_{G}(X), zbiór wszystkich drzew wyprowadzenia przez D_{G}.

Lemat 1 Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a, X ∈ V i w ∈ (Σ∪V)^{∗}. Nast_{}epuj _{}ace warunki s _{}a równoważne:

(i) X →^{G∗} w,

(ii) istnieje drzewo wyprowadzenia D ze zmiennej X, takie że y(D) = w.

Dowód.

(i) ⇒ (ii)

Niech X = w_{0} →^{G} w_{1} →^{G} … w_{k−1} →^{G} w_{k} = w b_{}edzie wyprowadzeniem słowa w ze zmiennej X. Dla ℓ = 0, 1, …, k, określamy kolejno drzewa wyprowadzenia D_{ℓ}, takie, że y(D_{ℓ}) = w_{ℓ}.

Drzewo D_{0} określamy nast_{}epuj _{}aco: dom(D_{0}) = {ϵ}, D_{0}(ϵ) = X.

Przypuśćmy, że jest już określone drzewo D_{ℓ}, ℓ < k i y(D_{ℓ}) = w_{ℓ}. Z definicji wyprowadzenia mamy w_{ℓ} = αY β i w_{ℓ+1} = αuβ, gdzie Y →^{G} u jest reguł _{}a przepisywania gramatyki G, a α, β ∈ (Σ ∪ V)^{∗}. Załóżmy, że w_{ℓ} = s_{1} … s_{m}, gdzie s_{1}, …, s_{m} ∈ Σ ∪ V, α = s_{1} … s_{i−1}, s_{i} = Y i β = s_{i+1} … s_{m}, dla pewnego i, 1 ≤ i ≤ m (gdy i = 1, α = ϵ, gdy i = m, β = ϵ). Niech v_{1}, …, v_{m′} b_{}ed _{}a tymi spośród liści drzewa D_{ℓ}, dla których D_{ℓ}(v_{i}) ≠ ϵ, w porz _{}adku leksykograficznym. Jest jasne, że m′ = m i D_{ℓ}(v_{j}) = s_{j}, dla j = 1, …, m. W szczególności, D_{ℓ}(v_{i}) = Y.

Rozróżnimy teraz dwa przypadki.

1. u = ϵ. Określamy drzewo D_{ℓ+1} nast_{}epuj _{}aco: dom(D_{ℓ+1}) = dom(D_{ℓ}) ∪ {v_{i}1}, D_{ℓ+1}(v) = D_{ℓ}(v) dla v ∈ dom(D_{ℓ}) oraz D_{ℓ+1}(v_{i}1) = ϵ.

2Liść v leksykograficznie poprzedza liść w jeśli istniej _{}a u ∈ ω^{∗}, i, j ∈ ω takie, że ui ≤ v, uj ≤ w i i < j.

2. u = u_{1} … u_{r}, r > 0. Określamy drzewo D_{ℓ+1} nast_{}epuj _{}aco: dom(D_{ℓ+1}) = dom(D_{ℓ}) ∪ {v_{i}1, …, v_{i}r}, D_{ℓ+1}(v) = D_{ℓ}(v) dla v ∈ dom(D_{ℓ}) oraz D_{ℓ+1}(v_{i}1) = u_{1}, …, D_{ℓ+1}(v_{i}r) = u_{r}.

Nietrudno sprawdzić, że D_{ℓ+1} jest drzewem wyprowadzenia i y(D_{ℓ+1}) = w_{ℓ+1}. (ii) ⇒ (i) Należy wykazać, że dla każdego drzewa wyprowadzenia D ∈ D_{X}, X →^{G∗} y(D). Dowód

poprowadzimy przez indukcj_{}e ze wzgl_{}edu na gł_{}ebokość drzewa D. Gdy D jest drzewem o gł_{}ebokości 0, to X = y(D) i oczywiście X →^{G∗} y(D). Załóżmy, że depth(D) ≥ 1, a wi_{}ec w korzeniu drzewa D została zastosowana pewna reguła X →^{G} u. Wówczas zachodzi jeden z dwóch przypadków.

1. u = ϵ i korzeń drzewa D (którym jest również ϵ) ma dokładnie jeden nast_{}epnik, mianowicie 1, przy czym D(1) = ϵ.

2. u = u_{1} … u_{r}, gdzie r > 0, u_{1}, …, u_{r} ∈ Σ ∪ V i korzeń ϵ ma dokładnie r nast_{}epników w drzewie D, mianowicie 1, …, r, przy czym D(i) = u_{i}, dla i = 1, …, r.

W pierwszym przypadku, oczywiście X →^{G∗} y(D) = ϵ.

Załóżmy drugi przypadek. Zauważmy najpierw, że o ile u_{i} = Y, to poddrzewo D.i wyznaczone przez wierzchołek i jest pewnym drzewem wyprowadzenia ze zmiennej Y, przy czym depth(D.i) < depth(D), a zatem, z założenia indukcyjnego, Y →^{G∗} y(D.i). Z kolei u możemy przedstawić u = α_{0}Z_{1}α_{1}Z_{2}α_{2} … Z_{m}α_{m}, gdzie, dla i = 0, 1, …, m, α_{i} ∈ Σ^{∗} (tzn. słowa α_{i} nie zawieraj _{}a zmiennych). Z definicji plonu, łatwo wynika, że

y(D) = α_{0}y(D_{1})α_{1}y(D_{2})α_{2} … y(D_{ℓ})α_{ℓ}

gdzie D_{i} jest poddrzewem wyznaczonym przez wierzchołek (nast_{}epnik korzenia) etykietowany Z_{i}.

Pami_{}etaj _{}ac o tym iż, jak już zauważyliśmy, Z_{i} →^{G∗} y(D_{i}), dla i = 1, …, ℓ, otrzymujemy

X →^{G} α_{0}Z_{1}α_{1}Z_{2}α_{2} … Z_{ℓ}α_{ℓ}
→^{G∗} α_{0}y(D_{1})α_{1}Z_{2}α_{2} … Z_{ℓ}α_{ℓ}
→^{G∗} α_{0}y(D_{1})α_{1}y(D_{2})α_{2} … Z_{ℓ}α_{ℓ}
…
→^{G∗} α_{0}y(D_{1})α_{1}y(D_{2})α_{2} … y(D_{ℓ})α_{ℓ}
= y(D)

□

Kiedy słowo w nie zawiera symboli nieterminalnych, to udowodniony przed chwil _{}a lemat możemy rozszerzyć o jeszcze jeden równoważny warunek: istnieje wyprowadzenie lewostronne słowa w.

Twierdzenie 1 Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a, i niech w ∈ Σ^{∗}. Nast_{}epuj _{}ace warunki s _{}a równoważne:

(i) istnieje wyprowadzenie słowa w ze zmiennej X,

(ii) istnieje maksymalne drzewo wyprowadzenia ze zmiennej X, którego plonem jest w,

(iii) istnieje wyprowadzenie lewostronne słowa w ze zmiennej X.

Dowód. Implikacja (i) ⇒ (ii) została udowodniona w Lemacie 1 (maksymalność drzewa jest oczywista, gdy plon nie zawiera symboli niekońcowych), a implikacja (iii) ⇒ (i) jest oczywista. Dla dowodu implikacji (ii) ⇒ (iii), wystarczy wykazać, że dla każdego drzewa wyprowadzenia D ∈ D_{X}, takiego że y(D) ∈ Σ^{∗}, X →^{lG∗} y(D). Dowód jest podobny do dowodu analogicznego faktu w dowodzie implikacji (ii) ⇒ (i) Lematu 1. W odpowiednim miejscu, kiedy dokonujemy rozkładu y(D) = α_{0}y(D_{1})α_{1}y(D_{2})α_{2} … y(D_{ℓ})α_{ℓ}, wystarczy zauważyć, że drzewa D_{i} s _{}a wtedy maksymalne i z założenia indukcyjnego mamy lewostronne wyprowadzenia Z_{i} →^{lG∗} y(D_{i}). □

2 Postaci normalne gramatyk bezkontekstowych

W tym rozdziale przedstawimy efektywn _{}a metod_{}e przekształcania gramatyki bezkontekstowej w równoważn _{}a gramatyk_{}e o stosunkowo prostej postaci, tzw. postaci normalnej Chomsky’ego. Jako produkt uboczny naszych rozważań uzyskamy także algorytm odpowiadaj _{}acy na pytanie, czy j_{}ezyk generowany przez gramatyk_{}e jest niepusty.

2.1 Eliminacja symboli nieużytecznych

Mówi _{}ac intuicyjnie, zmienn _{}a w gramatyce można uznać za nieużyteczn _{}a, kiedy nie da si_{}e jej osi _{}agn _{}ać w żadnym wyprowadzeniu z symbolu startowego, lub kiedy z niej nie można wyprowadzić żadnego słowa złożonego z symboli końcowych.

Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a. Powiemy, że zmienna Y jest osi _{}agalna ze zbioru zmiennych E ⊆ V, jeśli istniej _{}a X ∈ E oraz α, β ∈ (Σ ∪ V)^{∗}, takie że X →^{G∗} αY β.

Podobnie, jak to było dla automatu, określimy funkcj_{}e, dla E ⊆ V

Step(E) = {Y : (∃X ∈ E)(∃α, β ∈ (Σ ∪ V)^{∗})X →^{G} αY β}

Poniższy algorytm, podobny do Algorytmu 3 z Odcinka 1, oblicza zbiór zmiennych osi _{}agalnych z E.

Algorytm 5

Dane: Gramatyka G, zbiór zmiennych E ⊆ V

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

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

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

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

Wynik: zbiór X

Zauważmy, że linia 3 może być wykonana co najwyżej |V | razy (za każdym razem dokładamy coś do X), zatem algorytm na pewno si_{}e zatrzymuje po wykonaniu nie wi_{}ecej niż |V | obrotów p_{}etli 2. Ponadto, łatwo jest widzieć, że, na każdym etapie wykonywania algorytmu, wszystkie zmienne w zbiorze stanowi _{}acym wartość zmiennej X, s _{}a osi _{}agalne z E. Pozostaje wykazać, że w końcowej wartości zmiennej X znajduj _{}a si_{}e już wszystkie zmienne osi _{}agalne ze zbioru E. Istotnie, przypuśćmy, że zmienna Z jest osi _{}agalna z Y ∈ E przy pomocy wyprowadzenia

Y = w_{0} →^{G} w_{1} →^{G} … →^{G} w_{k−1} →^{G} w_{k} = αZβ

Wówczas można zaobserwować, że jeśli po wykonaniu p_{}etli (2.) i razy wszystkie zmienne wyst_{}epuj _{}ace w słowie w_{ℓ} znajduj _{}a si_{}e w wartości zmiennej X, to każda ze zmiennych wyst_{}epuj _{}acych w słowie w_{ℓ+1} znajdzie si_{}e w w wartości zmiennej X nie później niż po wykonaniu p_{}etli i + 1 razy. W szczególności zmienna Z znajdzie si_{}e w końcowej wartości zmiennej X.

Z kolei, powiemy, że zmienna X ∈ V jest produktywna, jeżeli X →^{G∗} w, dla pewnego w ∈ Σ^{∗}. Niech, dla u ∈ (Σ ∪ V)^{∗}, var(u) oznacza zbiór wszystkich zmiennych, które wyst_{}epuj _{}a w u. Określimy nast_{}epuj _{}ac _{}a funkcj_{}e na P (V),

BackStep(E) = {X : (∃u ∈ (Σ ∪ V)^{∗})(X →^{G} u ∧ var(u) ⊆ E)}

Zauważmy, że jeżeli wszystkie zmienne w zbiorze E s _{}a produktywne, to również wszystkie zmienne w zbiorze BackStep(E) s _{}a produktywne. Zauważmy także, że BackStep(∅) jest zbiorem tych zmiennych, z których w jednym kroku można wygenerować słowo złożone z symboli końcowych.

Nast_{}epuj _{}acy algorytm oblicza zbiór wszystkich zmiennych produktywnych:

Algorytm 6

Dane: Gramatyka G

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

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

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

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

Wynik: zbiór X

Tu również, podobnie jak w algorytmie 5, linia 3 może być wykonana co najwyżej |V | razy, zatem algorytm na pewno si_{}e zatrzymuje po wykonaniu nie wi_{}ecej niż |V | obrotów p_{}etli 2. Wykażemy, że końcowa wartość zmiennej X jest zbiorem wszystkich zmiennych produktywnych.

Istotnie, z własności funkcji BackStep wynika, że wartości, jakie zmienna X przyjmuje w trakcie wykonywania algorytmu s _{}a zbiorami zmiennych produktywnych. Pozostaje wykazać, że końcowa wartość zmiennej X obejmuje już wszystkie zmienne produktywne. W tym celu przypuśćmy, że Y jest zmienn _{}a produktywn _{}a i

Y = w_{0} →^{G} w_{1} … w_{k−1} →^{G} w_{k} = w

jest wyprowadzeniem pewnego słowa w ∈ Σ^{∗}. Wówczas można zaobserwować, że jeśli po wykonaniu p_{}etli (2.) i razy wszystkie zmienne wyst_{}epuj _{}ace w słowie w_{ℓ}, ℓ > 0, znajduj _{}a si_{}e w wartości zmiennej X, to każda ze zmiennych wyst_{}epuj _{}acych w słowie w_{ℓ−1} znajdzie si_{}e w w wartości zmiennej X nie później niż po wykonaniu p_{}etli i+1 razy. W szczególności zmienna Y znajdzie si_{}e w końcowej wartości zmiennej X.

Zauważmy, że L(G) ≠ ∅ wtedy i tylko wtedy, gdy symbol startowy X_{I} jest zmienn _{}a produktywn _{}a. Mamy wi_{}ec

Fakt 1 Istnieje algorytm, który, dla danej gramatyki bezkontekstowej G rozstrzyga, czy L(G) ≠ ∅. □

Przedstawione wyżej algorytmy zastosujemy teraz dla sprowadzenia gramatyki do takiej postaci, w której nie ma symboli nieużytecznych.

Mówimy, że gramatyki G i H s _{}a równoważne, kiedy L(G) = L(H).

Fakt 2 Dla każdej gramatyki G takiej, że L(G) ≠ ∅ można skonstruować równoważn _{}a gramatyk_{}e G′, w której każda zmienna jest produktywna i osi _{}agalna z symbolu pocz _{}atkowego.

Dowód. Jeśli G = (Σ, V, X_{I}, R) jest gramatyk _{}a i E ⊆ V, X_{I} ∈ E, to przez obci_{}ecie gramatyki G do zbioru E rozumiemy gramatyk_{}e G|E =_{df} (Σ, E, X_{I}, R′), gdzie R′ = R ∩ (E × (Σ ∪ E)^{∗}). (Innymi słowy, reguła Y → w gramatyki G pozostaje reguł _{}a gramatyki G|E, o ile Y ∈ E i var(w) ⊆ E.) Niech E b_{}edzie zbiorem wszystkich zmiennych produktywnych gramatyki G. Z założenia, X_{I} ∈ E. Oczywiście, gramatyka G|E jest równoważna gramatyce G. (Wszystkie zmienne wyst_{}epuj _{}ace w wyprowadzeniu słowa w ∈ Σ^{∗} w gramatyce G musz _{}a być produktywne.) Z kolei, niech E′ ⊆ E b_{}edzie zbiorem tych zmiennych, które s _{}a osi _{}agalne z X_{I} w gramatyce G|E. Rozważmy gramatyk_{}e (G|E)|E′. Łatwo widzieć, że gramatyka ta jest równoważna gramatyce G|E (a wi_{}ec i G) i, oczywiście, wszystkie zmienne tej gramatyki s _{}a w niej osi _{}agalne z X_{I}. Z drugiej strony, nietrudno wykazać, że każda zmienna z E′, która była produktywna w G, jest nadal produktywna w (G|E)|E′. Zatem gramatyka (G|E)|E′ spełnia ż _{}adane warunki. □

Przykład 2 Niech

G = ({a}, {X, Y, Z}, X, {(X, ϵ), (X, Y Z), (Z, ϵ)})

Wszystkie zmienne s _{}a osi _{}agalne z X, ale zmienna Y jest nieproduktywna. Stosuj _{}ac konstrukcj_{}e z powyższego dowodu, otrzymujemy

G|E = ({a}, {X, Z}, X, {(X, ϵ), (Z, ϵ)})

i

(G|E)|E′ = ({a}, {X}, X, {(X, ϵ)})

Zauważmy, że gdybyśmy odwrócili kolejność wykonywanych operacji i najpierw ograniczyli gramatyk_{}e G do zmiennych osi _{}agalnych z X, a nast_{}epnie do zmiennych produktywnych, to otrzymalibyśmy kolejno gramatyki G i G|E, a zatem taka konstrukcja nie byłaby poprawna.

Eliminacja trywialnych reguł

Reguł_{}e postaci X →^{G} ϵ nazywamy krótko ϵ-reguł _{}a.

Fakt 3 (eliminacja ϵ-reguł) Dla każdej gramatyki G, można skonstruować gramatyk_{}e G′ bez ϵ-reguł, tak _{}a, że L(G′) = L(G) − {ϵ}.

Dowód. Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a. Zmienn _{}a X ∈ V nazwiemy zerowaln _{}a, jeśli X →^{G∗} ϵ. Zbiór zmiennych zerowalnych można wyznaczyć efektywnie przy pomocy procedury podobnej do algorytmu obliczania zbioru zmiennych produktywnych (Algorytm 6); szczegóły pozostawiamy Czytelnikowi.

Zauważmy, że nie wystarczy po prostu usun _{}ać wszystkie ϵ-reguły, bo w ten sposób moglibyśmy przy okazji uniemożliwić niektóre wyprowadzenia słów różnych od ϵ (np. gdy produkcje s _{}a X → Y Z, Y → ϵ, Z → a, to, usuwaj _{}ac reguł_{}e Y → ϵ, uniemożliwimy wyprowadzenie X →^{∗} a).

Przedstawimy dwa sposoby, z których pierwszy jest bardziej bezpośredni i łatwy do zrozumienia, ale drugi bardziej ekonomiczny.

Sposób 1

Usuwamy ze zbioru R wszystkie ϵ-reguły, a nast_{}epnie, dla każdej reguły X → α dodajemy wszystkie reguły, jakie można utworzyć zast_{}epuj _{}ac w α dowolne zmienne zerowalne przez ϵ z wyj _{}atkiem (jeśli taka reguła mogłaby powstać) reguły X → ϵ.

Dowód, że, dla każdego w ≠ ϵ,

X →^{G∗} w ⇔ X →^{G′∗} w

można przeprowadzić przez indukcj_{}e ze wzgl_{}edu na gł_{}ebokość drzewa wyprowadzenia.

Sposób 2

Objaśnimy go na przykładzie. Tu również na pocz _{}atku usuwamy ϵ-reguły. Dalej, przypuśćmy, że mamy regułe X → Z_{1} … Z_{m} i wszystkie zmienne Z_{1}, …, Z_{m} s _{}a zerowalne. Wprowadzamy nowe zmienne [Z_{1}Z_{2} … Z_{m}], [Z_{2}Z_{3} … Z_{m}], …, [Z_{m−1}Z_{m}], [Z_{m}] i dodajemy nast_{}epuj _{}ace reguły:

\begin{aligned}X & → & Z_{i} & i = 1, …, m \\ X & → & Z_{i}[Z_{i+1}Z_{i+2} … Z_{m}] & i = 1, …, m \\ [Z_{i}Z_{i+1} … Z_{m}] & → & Z_{j} & i = 1, …, m − 1, j = i, i + 1, …, m \\ [Z_{i}Z_{i+1} … Z_{m}] & → & Z_{j}[Z_{j+1}Z_{j+2} … Z_{m}] & i = 1, …, m − 1, j = i, i + 1, …, m \end{aligned}

Zauważmy, że stosuj _{}ac pierwszy sposób, zast _{}apilibyśmy regułe X → Z_{1} … Z_{m} przez 2^{m}−1 reguł, a przy drugim sposobie przez O(m^{2}) reguł. □

Reguł_{}e postaci X →^{G} Y nazywamy reguł _{}a jednostkow _{}a.

Lemat 2 Dla każdej gramatyki G, takiej, że L(G) ≠ ∅ i ϵ ∉ L(G), można skonstruować równoważn _{}a gramatyk_{}e bez reguł jednostkowych, bez ϵ-reguł i tak _{}a, że każda zmienna jest produktywna i osi _{}agalna z symbolu pocz _{}atkowego.

Dowód. Niech G = (Σ, V, X_{I}, R) b_{}edzie gramatyk _{}a. Na mocy Faktu 3, możemy założyć, że G jest już bez ϵ-reguł.

Usuwamy z R wszystkie reguły jednostkowe, natomiast dla każdych X, Y, jeśli X →^{G∗} Y i Y → α, gdzie α jest różne od zmiennej, dokładamy reguł_{}e X → α. Zauważmy, że możemy łatwo rozstrzygn _{}ać czy X →^{G∗} Y w |V | krokach, ponieważ nie ma ϵ-reguł.

Niech R′ b_{}edzie otrzymanym zbiorem reguł.

Oczywiście, nie dodaliśmy żadnej ϵ–reguły.

Dla zapewnienia ostatniego z warunków Lematu, stosujemy procedur_{}e z dowodu Faktu 2, która eliminuje ewentualne symbole nieużyteczne. □

2.2 Twierdzenia o postaci normalnej gramatyk

Twierdzenie 2 (o postaci normalnej Chomsky’ego) Dla każdej gramatyki G, takiej, że L(G) ≠ ∅ i ϵ ∉ L(G), można skonstruować równoważn _{}a gramatyk_{}e, w której każda reguła jest postaci X → σ, gdzie σ ∈ Σ, lub X → Y Z, gdzie Y, Z ∈ V (X, Y, Z nie musz _{}a być różne).

Dowód. Dla każdego σ ∈ Σ, tworzymy now _{}a zmienn _{}a Z_{σ} i do zbioru reguł gramatyki G dokładamy reguł_{}e Z_{σ} → σ. Na mocy Lematu 2, możemy założyć, że każda reguła gramatyki G, która nie jest postaci X → σ, jest postaci X → α, |α| ≥ 2. Modyfikujemy t_{}e reguł_{}e zast_{}epuj _{}ac w α każde σ ∈ Σ przez Z_{σ}. W ten sposób otrzymujemy gramatyk_{}e, w której każda reguła jest postaci X → σ, σ ∈ Σ, lub X → Z_{1} … Z_{m}, gdzie Z_{1}, …, Z_{m} ∈ V, m ≥ 2. Jeżeli m > 2, to wprowadzamy nowe zmienne [Z_{2}Z_{3} … Z_{m}], …, [Z_{m−1}Z_{m}] i reguły

X → Z_{1}[Z_{2}Z_{3} … Z_{m}]
[Z_{i} … Z_{m}] → Z_{i}[Z_{i+1} … Z_{m}] dla i < m − 1
[Z_{m−1}Z_{m}] → Z_{m−1}Z_{m}

□

Pytanie. Jeśli gramatyka G jest w postaci Chomsky’ego, to jak możemy oszacować z góry długość wyprowadzenia słowa w ∈ L(G), w zależności od długości w ?

W uzupełnieniu powyższego twierdzenia, podamy dla informacji, bez dowodu, inne twierdzenie o postaci normalnej, którego autorem jest pani S.Greibach.

Twierdzenie 3 (o postaci normalnej Greibach) Dla każdej gramatyki G, takiej, że L(G) ≠ ∅ i ϵ ∉ L(G), można skonstruować równoważn _{}a gramatyk_{}e, w której każda reguła jest postaci X → σα, gdzie σ ∈ Σ i α ∈ V^{∗}.

2.3 Algorytm rozpoznawania j_{}ezyków bezkontekstowych

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

Dane Gramatyka G, słowo w ∈ Σ^{∗} Pytanie Czy w ∈ L(G)?

Jeśli w = ϵ to problem możemy rozwi _{}azać obliczaj _{}ac zbiór zmiennych ϵ-produktywnych, tzn. takich, że X →^{G∗} ϵ podobnie jak obliczaliśmy zbiór zmiennych produktywnych w Algorytmie 6 (str. 9), z tym, że w funkcji Back-Step bierzemy pod uwag_{}e tylko te reguły w których nie wyst_{}epuj _{}a w ogóle symbole terminalne.

Ciekawszy jest przypadek, gdy |w| > 0.

Moglibyśmy wówczas znaleźć gramatyk_{}e Chomsky’ego G′ generuj _{}ac _{}a L(G) − {ϵ} i przeszukiwać wszystkie wyprowadzenia o ograniczonej długości (por. “Pytanie” powyżej). Metoda ta byłaby jednak zupełnie nieefektywna.

Poniżej naszkicujemy algorytm zaproponowany przez Cocke’a, Youngera i Kasamiego, i od nazwisk autorów zwany algorytmem CYK, który rozwi _{}azuje zadanie w czasie wielomianowym.

W algorytmie tym zakładamy, że G = (Σ, V, X_{I}, R) jest już w postaci Chomsky’ego (por. Ćwiczenie 12 poniżej). Niech w = w_{1} … w_{n}, gdzie w_{1}, …, w_{n} ∈ Σ. Główn _{}a prac _{}a algorytmu jest indukcyjne obliczanie tablicy zbiorów V_{i,j}, i = 1, …, n, j = 1, …, n+1−i, gdzie

V_{i,j} = {X : X →^{G∗} w_{i}w_{i+1} … w_{i+j−1}} (*)

Nast_{}epuj _{}aca obserwacja jest kluczowa dla algorytmu:

jeśli Y ∈ V_{i,j}, Z ∈ V_{i+j,k} i X →^{G} Y Z, to X ∈ V_{i,k}.

Ostateczna odpowiedź na pytanie zależy oczywiście od tego, czy X_{I} ∈ V_{1,n}. Przyjmijmy oznaczenie, dla zbiorów zmiennych A, B ⊆ V,

Fusion(A, B) = {X : (∃Y, Z) X →^{G} Y Z ∧ Y ∈ A ∧ Z ∈ B}

Wówczas algorytm CYK można przedstawić nast_{}epuj _{}aco.

Algorytm CYK Dane: Gramatyka G w postaci Chomsky’ego, słowo w = w_{1} … w_{n}

1. Dla i = 1, …, n, wykonuj : V_{i,1} := {X : X →^{G} w_{i}};

2. Dla j = 2, …, n, wykonuj :

3. Dla i = 1, …, n + 1 − j, wykonuj :

4. V_{i,j} := ∅;

5. Dla k = 1, …, j − 1, wykonuj :

6. V_{i,j} := V_{i,j} ∪ Fusion(V_{i,k}, V_{i+k,j−k}).

Nietrudno wykazać, że po wykonaniu dla danego j instrukcji 3–6, zawartość zmiennej V_{i,j} (dla każdego i, takiego że j ≤ n + 1 − i) spełnia warunek (*). Zatem w ∈ L(G) wtedy i tylko wtedy, gdy po zakończeniu pracy algorytmu X_{I} ∈ V_{1,n}.

Czas wykonania operacji Fusion przy odpowiedniej implementacji możemy oszacować przez rozmiar gramatyki rozumiany jako ł _{}aczna długość wszystkich produkcji, |G|. Zatem cały algorytm działa w czasie O(n^{3} · |G|), gdzie n = |w|.

Ćwiczenia

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

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

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

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

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

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

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

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

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

(i) {a, b}^{∗} − {ww : w ∈ {a, b}^{∗}}.

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

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

(a) L jest regularny,

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

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

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

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

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

6. Dla dowolnej gramatyki G oszacować z góry liczb_{}e reguł gramatyki Chomsky’ego generuj _{}acej j_{}ezyk L(G) − {ϵ}, jak _{}a otrzymamy przez konstrukcje opisane w punkcie 2.2.

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

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

9. Oszacować czas działania powyższego Algorytmu 6 (str. 9) oraz wynikaj _{}acego zeń algorytmu rozstrzygaj _{}acego, dla danej gramatyki G, czy L(G) ≠ ∅.

10. Oszacować długość najkrótszego słowa generowanego przez gramatyk_{}e G

(a) jeśli G jest w postaci Chomsky’ego,

(b) w dowolnym przypadku.

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

12. Dowieść, że procedury sprowadzania dowolnej gramatyki bezkontekstowej do postaci Chomsky’ego opisane w punktach 2.1 i 2.2 można przeprowadzić w czasie wielomianowym wzgl_{}edem oryginalnej gramatyki. Oszacować rozmiar otrzymanej gramatyki.

Uwaga: Jeśli oryginalna gramatyka generuje słowo puste, możemy znaleźć gramatyk_{}e Chomsky’ego dla L(G) − {ϵ} i dodać reguł_{}e X_{I} → ϵ.