Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne

Wprowadzimy i udowodnimy najprostszą wersję lematu o pompowaniu dla języków bezkontekstowych.

Lemat o pompowaniu


Istotną cechą języków regularnych jest własność pompowania, którą ustaliliśmy w lemacie o pompowaniu. Podobną, ale nie taką samą, cechę posiadają języki bezkontekstowe. O ile dla języków regularnych własność pompowania wynikała z istnienia pętli w grafie opisującym automat, to dla języków bezkontekstowych pompowanie jest wynikiem powtarzającego się symbolu nieterminalnego w wyprowadzeniu dostatecznie długiego słowa w gramatyce.

Lemat 1.1

(o pompowaniu) Dla dowolnego języka bezkontekstowego \(\displaystyle L \subset A^*\) istnieją liczby naturalne \(\displaystyle N,M \geqslant 1\) takie, że każde słowo \(\displaystyle w \in L\) o długości \(\displaystyle |w| > N\) można przedstawić w formie \(\displaystyle w=u_1w_1uw_2u_2\), gdzie \(\displaystyle w_{1,}w_{2},v_{1},v_{2},u\in A^{*}\) oraz

  1. \(\displaystyle |w_1uw_2| \leqslant M\)
  2. \(\displaystyle w_1w_2 \neq 1\)
  3. \(\displaystyle u_1w_1^iuw_2^iu_2 \in L\) dla \(\displaystyle i=0,1,...\)

Zanim przeprowadzimy dowód lematu, zobaczmy jak stosuje się ten lemat do języka generowanego przez gramatykę \(\displaystyle (\{v_0,v_1,v_2 \},\{a,b\},v_0,P)\),
gdzie \(\displaystyle P: v_0 \rightarrow v_1v_2, \;v_1 \rightarrow av_2 b , v_2 \rightarrow b\;|\;v_0b.\)

Animacja 1

Dowód

Załóżmy, bez utraty ogólności rozważań (dlaczego?), że język bezkontekstowy \(\displaystyle L\) nie zawiera słowa pustego i jest generowany przez gramatykę \(\displaystyle G=(V_N,V_T,v_0,P)\) w normalnej postaci Chomsky'ego. Rozważmy dowolne wyprowadzenie w \(\displaystyle G\)

\(\displaystyle w_0 \mapsto w_1 \mapsto ... \mapsto w_r\)

o długości \(\displaystyle r \geqslant 1\) i \(\displaystyle w_0 \in V_N\). Niech najdłuższa ścieżka w drzewie binarnym \(\displaystyle T\) tego wyprowadzenia ma długość \(\displaystyle k\) (jako długość przyjmujemy tutaj liczbę wierzchołków, przez które przechodzi ścieżka). Indukcyjne ze względu na \(\displaystyle k\) łatwo jest uzasadnić, że

\(\displaystyle |w_r| \leqslant 2^{k-1}.\)

Załóżmy teraz, że zbiór \(\displaystyle V_N\) ma \(\displaystyle p\) elementów i przyjmijmy \(\displaystyle N=2^p\) oraz \(\displaystyle M=2^{p+1}\). Niech \(\displaystyle w \in L(G)\) będzie słowem, którego długość jest większa od \(\displaystyle N\). Zatem najdłuższa ścieżka \(\displaystyle S\) w drzewie wyprowadzenia \(\displaystyle T\) będącego wyprowadzeniem słowa \(\displaystyle w\) w gramatyce \(\displaystyle G\) ma długość co najmniej \(\displaystyle p+2\). A więc przechodzi przez co najmniej \(\displaystyle p+2\) wierzchołków. Stąd, że wierzchołki maksymalne drzewa wyprowadzenia mają etykiety terminalne, wnioskujemy, że w \(\displaystyle S\) występują dwa różne wierzchołki \(\displaystyle s_1, s_2\) etykietowane przez ten sam symbol nieterminalny \(\displaystyle v\). Przyjmijmy, że wierzchołek \(\displaystyle s_1\) jest bliższy wierzchołka początkowego drzewa wyprowadzenia niż \(\displaystyle s_2\). Wierzchołki \(\displaystyle s_1, s_2\) można tak dobrać, aby podścieżka ścieżki \(\displaystyle S\) o początku w wierzchołku \(\displaystyle s_1\) miała długość równą co najwyżej \(\displaystyle p+2\). Zauważmy teraz, że żadna ścieżka poddrzewa \(\displaystyle T_1\), którego wierzchołkiem początkowym jest \(\displaystyle s_1\), nie ma długości większej niż \(\displaystyle p+2\). Jeśli więc \(\displaystyle \overline w\) jest słowem określonym przez liście \(\displaystyle T_1\), to

\(\mbox{(1)}\)

\(\displaystyle |\overline{w}|\leqslant 2^{(p+2)-1}=M.\)

Rozważmy teraz poddrzewo \(\displaystyle T_2\) drzewa \(\displaystyle T\) o wierzchołku początkowym w \(\displaystyle s_2\) i niech \(\displaystyle u\) będzie słowem określonym przez liście \(\displaystyle T_2\). Wtedy \(\displaystyle \overline w= w_1uw_2\) dla pewnych \(\displaystyle w_1, w_2 \in V_T^*\). W połączeniu z nierównością \(\mbox{(1)}\) uzyskujemy pierwszą własność postulowaną w lemacie. Co więcej, \(\displaystyle w_1w_2 \neq 1,\) ponieważ pierwsza produkcja wyprowadzenia \(\displaystyle v\mapsto^{*}\overline{w}\) jest postaci \(\displaystyle v \rightarrow v_1v_2\) dla pewnych \(\displaystyle v_{1},\, v_{2}\in V_{N}\) , a w gramatyce nie ma produkcji wymazującej. Zatem dla pewnych \(\displaystyle u_1, u_2 \in V^*_T\) jest

\(\displaystyle v_{0}\mapsto^{*}u_{1}vu_{2}\mapsto^{*}u_{1}uu_{2}\)

lub

\(\displaystyle v_0 \mapsto^* u_1vu_2 \mapsto^* u_1w_1vw_2u_2 \mapsto^* u_1 w_1 uw_2 u_2 = w\)

lub

\(\displaystyle v_{0}\mapsto^{*}u_{1}vu_{2}\mapsto^{*}u_{1}w_{1}vw_{2}u_{2}\mapsto^{*}u_{1}w^{i}_{1}vw^{i}_{2}u_{2}\mapsto^{*}u_{1}w^{i}_{1}uw^{i}_{2}u_{2}\)

dla \(\displaystyle i=1,2,\ldots\)

W konsekwencji \(\displaystyle u_1w_1^iuw_2^iu_2 \in L\) dla dowolnego \(\displaystyle i=0,1,...\). Lemat zatem został udowodniony.

Analogicznie jak w przypadku języków regularnych, lemat o pompowaniu dla języków bezkontekstowych stosuje się najczęściej do zasadnienia,
że pewne języki nie należą do rodziny \(\displaystyle \mathcal{L}_{2}.\) Takie właśnie zastosowanie przedstawione jest poniżej, na przykładzie
języka, o którym pó{z}niej udowodnimy, że jest kontekstowy, czyli należy do rodziny języków \(\displaystyle \mathcal{L}_{1}.\)

Przykład 1.1

Niech \(\displaystyle L=\{a^nb^nc^n : n \geqslant 1 \}\). Przeprowadzając rozumowanie nie wprost, a więc zakładając bezkontekstowość tego języka, z lematu o pompowaniu uzyskujemy odpowiednie stałe \(\displaystyle M, N\). Niech \(\displaystyle k > \frac{N}{3}\) i rozważmy słowo \(\displaystyle x_1=a^kb^kc^k\). Zatem istnieje rozkład \(\displaystyle x_1=u_1w_1uw_2u_2\), \(\displaystyle w_1w_2 \neq 1\) oraz \(\displaystyle x_i=u_1w_1^iuw_2^iu_2 \in L\) dla \(\displaystyle i=0,1,...\) Z postaci słów języka \(\displaystyle L\) oraz z faktu \(\displaystyle w_1w_2 \neq 1\) wnioskujemy, że słowa \(\displaystyle w_1, w_2\) są potęgami jednej z liter \(\displaystyle a,b,c\) oraz że \(\displaystyle |x_i| \longrightarrow \infty\), o ile \(\displaystyle i \longrightarrow \infty\). A to wyklucza możliwość zachowania własności określającej język \(\displaystyle L\). Otrzymana sprzeczność prowadzi do wniosku, iż język \(\displaystyle \{a^nb^nc^n: n \geqslant 1 \}\) nie jest bezkontekstowy.

Lemat o pompowaniu wykorzystywany bywa również w dowodach rozstrzygalności pewnych problemów w rodzinie języków rozpoznawalnych. Zagadnieniem tym zajmiemy się w dalszej części tego wykładu.

Własności rodziny języków bezkontekstowych


Przedstawimy teraz podstawowe własności rodziny języków bezkontekstowych związane z zamkniętością ze względu na działania oraz
z problemami jednoznaczności.

Twierdzenie 2.1

Rodzina języków bezkontekstowych \(\displaystyle \mathcal{L}_{2}\) jest zamknięta ze względu na następujące działania:

  1. sumę mnogościową,
  2. katenację i operację iteracji \(\displaystyle *\),
  3. przecięcie (iloczyn mnogościowy) z językiem regularnym,
  4. homomorfizm.

Dowód

1. Niech \(\displaystyle G_i = (V^i_N ,V_T,v^i_0,P_i)\) będą gramatykami bezkontekstowymi dla \(\displaystyle i=1,2\) takimi, że \(\displaystyle V^1_N \cap V^2_N = \emptyset\) oraz \(\displaystyle L_i = L(G_i)\). Język \(\displaystyle L = L_1 \cup L_2\) jest generowany przez gramatykę bezkontekstową określoną w następujący sposób:

\(\displaystyle G= (V^1_N \cup V^2_N \cup \{v_0\},V_T,v_0,P^1 \cup P^2 \cup \{ v_0 \rightarrow v^1_0 , v_0 \rightarrow {v_0}^2 \}).\)

2. Przy powyższych oznaczeniach, język \(\displaystyle L = L_1 \cdot L_2\) jest generowany przez gramatykę bezkontekstową:

\(\displaystyle G= (V^1_N \cup V^2_N \cup \{ v_0 \},V_T,v_0,P^1 \cup P^2 \cup \{ v_0 \rightarrow v^1_0 v^2_0 \}).\)

Jeśli \(\displaystyle L = L(G)\), dla \(\displaystyle G = (V_N ,V_T,v_0,P)\) gramatyki bezkontekstowej, to \(\displaystyle L^* = L(\overline{G})\) dla gramatyki

\(\displaystyle \overline{G} = ( V_N \cup \{\overline{v}_0 \} , V_T , \overline{v}_0,P \cup \{ \overline{v}_0 \rightarrow 1 , \overline{v}_0 \rightarrow \overline{v}_0 v_0 \},\)

która jest również gramatyką bezkontekstową.

3. Niech \(\displaystyle R\) będzie dowolonym językiem rozpoznawanym przez pewien automat skończenie stanowy \(\displaystyle \mathcal{A} \displaystyle =(S,f,s_0,T)\). Język ten możemy przedstawić w postaci sumy \(\displaystyle R=\bigcup_{i=1}^k R_i\), w której każdy język \(\displaystyle R_i\) jest rozpoznawany przez automat \(\displaystyle \mathcal{A}\) , w którym jako stan końcowy przyjmujemy \(\displaystyle t_i \in T\). Rodzina języków bezkontekstowych jest zamknięta ze względu na sumę mnogościową i oczywista jest równość \(\displaystyle L \cap R= \bigcup _{i=1}^k (L \cap R_i)\). Wystarczy zatem udowodnić, że język \(\displaystyle L \cap R_i\) jest bezkontekstowy. Załóżmy, że \(\displaystyle T=\{t \}\) oraz \(\displaystyle L\) jest językiem generowanym przez gramatykę bezkontekstową \(\displaystyle G = (V_N ,V_T,v_0,P)\) w normalnej postaci Chomsky'ego. Bez utraty ogólności rozważań można także założyć, że \(\displaystyle 1\notin L\). Konstruujemy gramatykę

\(\displaystyle H=(S \times (V_N \cup V_T) \times S,V_T,(s_0,v_0,t),P_H),\)

dla której \(\displaystyle P_H\) zawiera następujące produkcje:

  • \(\displaystyle (s_1,v_1,s_2) \rightarrow (s_1,v_2,s_3)(s_3,v_3,s_2)\) dla \(\displaystyle s_i \in S\), \(\displaystyle v_i \in V_N\) jeśli \(\displaystyle v_1\rightarrow v_2v_3 \in P,\)
  • \(\displaystyle (s_1,v_1,s_2) \rightarrow (s_1,a,s_2)\) dla \(\displaystyle s_i \in S\), \(\displaystyle a \in V_T\) jeśli \(\displaystyle v_1\rightarrow a \in P,\)
  • \(\displaystyle (s_1,a,s_2)\rightarrow a\) dla \(\displaystyle s_i \in S\), \(\displaystyle a \in V_T\) jeśli \(\displaystyle f(s_1,a)=s_2.\)

Bezpośrednio z konstrukcji wynika, że gramatyka \(\displaystyle H\) jest bezkontekstowa. Łatwo również zauważyć, że język generowany przez gramatykę \(\displaystyle H\) jest równy \(\displaystyle L \cap R\).

4. Niech \(\displaystyle h: A^* \longrightarrow B^*\) oznacza dowolny homomorfizm, a \(\displaystyle L \subset A^*\) językiem bezkontekstowym generowanym przez gramatykę \(\displaystyle G = (V_N ,A,v_0,P)\). Rozszerzamy homomorfizm \(\displaystyle h\) do wolnych monoidów \(\displaystyle (A \cup V_N)^*\) i \(\displaystyle (B \cup V_N)^*\), przyjmując, że \(\displaystyle h\) na zbiorze \(\displaystyle V_N\) jest równe identyczności. Łatwo zauważyć, że język \(\displaystyle h(L)\) jest generowany przez gramatykę bezkontekstową \(\displaystyle G = (V_N, B, v_0, P_h)\), w której

\(\displaystyle P_h=\{ v \rightarrow h(w): v \rightarrow w \in P \}.\)

Z równości \(\displaystyle L\setminus R=L\cap \overline{R}\) , zamkniętości klasy \(\displaystyle \mathcal{L}_{3}\) ze względu na zupełnienie
oraz z punktu 3 udowodnionego powyżej twierdzenia wynika następujący wniosek.

Wniosek 2.1

Niech \(\displaystyle L \subset A^*\) będzie dowolonym językiem bezkontekstowym, a \(\displaystyle R \subset A^*\) regularnym. Wtedy \(\displaystyle L \setminus R\) jest językiem bezkontekstowym.

Bez dowodu podajemy dwie dalsze własności związane z zamkniętością rodziny języków bezkontekstowych.

Fakt 2.1

Rodzina języków bezkontekstowych \(\displaystyle \mathcal{L}_{2}\) jest zamknięta ze względu na podstawienie regularne i przeciwobraz przez homomorfizm.

Rodzina języków bezkontekstowych nie jest zamknięta na wszystkie działania boolowskie. Jak wynika z poniższego twierdzenia, jedynym działaniem boolowskim nie wyprowadzającym poza rodzinę języków bezkontekstowych jest suma mnogościowa.

Twierdzenie 2.2

Rodzina języków bezkontekstowych \(\displaystyle \mathcal{L}_{2}\) nie jest zamknięta ze względu na:

  1. iloczyn mnogościowy,
  2. uzupełnienie.

Dowód

Dla \(\displaystyle i=1,2\) niech \(\displaystyle G_i = (\{ v_0 , v_1\},\{ a,b,c\},{v_0},P_i)\) będą gramatykami o następujących zbiorach praw:

\(\displaystyle \begin{array} {l} P_1 = \{ v_0 \rightarrow v_0 c, \; v_0 \rightarrow v_1 c, \; v_1 \rightarrow ab, \; v_1 \rightarrow a v_1 b \}, \\ P_2 = \{ v_0 \rightarrow a v_0 , \; v_0 \rightarrow a v_1 , \; v_1 \rightarrow bc, \; v_1 \rightarrow b v_1 c \}. \end{array}\)

Gramatyki te są bezkontekstowe i generują, odpowiednio, następujące języki:

\(\displaystyle L(G_{1})=\left\{ a^{n}b^{n}c^{m}:n,m\geqslant 1\right\} \in \mathcal{L}_{2},\)

\(\displaystyle L(G_{2})=\left\{ a^{n}b^{m}c^{m}:n,m\geqslant 1\right\} \in \mathcal{L}_{2}.\)

Języki te są bezkontekstowe, lecz ich przecięcie

\(\displaystyle L(G_{1})\cap L(G_{2})=\left\{ a^{n}b^{n}c^{n}\, :\, n\geqslant 1\right\} \notin \mathcal{L}_{2}\)

jest językiem istotnie kontekstowym.

Z udowodnionej właśnie własności oraz z praw de'Morgana wynika, że rodzina \(\displaystyle \mathcal{L}_{2}\) nie jest też domknięta ze względu na uzupełnienie.

Jednoznaczność języków bezkontekstowych


Omówimy teraz, dość ogólnie zresztą, problem występujący w niektórych gramatykach bezkontekstowych, a polegający na wielokrotnym wyprowadzeniu tego samego słowa. Z punktu widzenia języków programowania, których syntaktykę opisują, w pewnym zakresie, gramatyki bezkontekstowe, taka nadmiarowość (niejednoznaczność parsingu) jest cechą wysoce niepożądaną. Gramatyki, które nie będą mieć takiej własności nazwiemy jednoznacznymi. Jednoznacznym nazwiemy też język, dla którego istnieje gramatyka jednoznaczna.

Definicja 3.1

Niech \(\displaystyle G = (V_N,V_T,v_0,P)\) będzie gramatyką bezkontekstową. Lewostronnym (prawostronnym) wyprowadzeniem słowa \(\displaystyle w \in {V_T}^*\) w gramatyce \(\displaystyle G\) nazywamy wyprowadzenie

\(\displaystyle v_0 \mapsto w_1 \mapsto \ldots.. \mapsto w_n = w\) takie, że dla każdego \(\displaystyle i=0,\ldots,n-1, \;\; w_{i+1}\) jest generowane bezpośrednio z \(\displaystyle w_i\) przez zastąpienie pierwszego z lewej (prawej) symbolu nieterminalnego występującego w słowie \(\displaystyle w_i\).

Jeśli chcemy zaznaczyć, że wyprowadzenie jest lewostronne lub prawostronne, to posługujemy się zapisem

\(\displaystyle v_{0}\mapsto_{L}^{*}w,\; v_{0}\mapsto_{P}^{*}w.\)

Każde wyprowadzenie słowa w gramatyce bezkontekstowej można tak uporządkować, by sekwencja produkcji tworzyła prawostronne lub lewostronne wyprowadzenie. Stąd wynika też fakt, że dowolne słowo generowane przez gramatykę bezkontekstową ma tyle samo wyprowadzeń lewostronnych, co prawostronnych. Ilość różnych wyprowadzeń danego słowa jest w niektórych zastosowaniach gramatyk bezkontekstowych dość istotna, choćby w problemach parsingu, czyli poszukiwania w gramatyce wyprowadzenia dla danego słowa. Ilość różnych wyprowadzeń słów w gramatyce stanowi pewną informację na temat nadmiarowości tej gramatyki. Bardzo istotną rolę odgrywają zarówno w teorii, jak i zastosowaniach - gramatyki bezkontekstowe jednoznaczne, których definicję podajemy poniżej.

Definicja 3.2

Gramatyka bezkontekstowa \(\displaystyle G\) jest jednoznaczna wtedy i tylko wtedy, gdy każde słowo generowane przez tę gramatykę ma dokładnie jedno wyprowadzenie lewostronne (prawostronne). Język bezkontekstowy \(\displaystyle L\) nazywamy jednoznacznym, jeśli istnieje jednoznaczna gramatyka bezkontekstowa generująca ten język.

Jednoznaczność gramatyki oznacza istnienie dokładnie jednego drzewa wywodu dla każdego generowanego słowa. W klasie gramatyk bezkontekstowych problem jednoznaczności jest nierozstrzygalny. W rozdziale poświęconym algorytmicznej rozstrzygalności wrócimy do tego zagadnienia. Oczywiście wobec powyższego nierozstrzygalny jest też problem jednoznaczności języka. Problem jednoznaczności gramatyki i języka jest rozstrzygalny w podklasach języków bezkontekstowych, na przykład dla klasy języków ograniczonych, to znaczy takich
\(\displaystyle L\subset A^{*}\) , że \(\displaystyle L\subset w_{1}^{*}...w_{n}^{*}\) dla pewnych słów \(\displaystyle w_{1},...,w_{n}\in A^{*}\) .

Przykład 3.1

Język \(\displaystyle \left\{ a^{n}b^{n+m}c^m\, :\, n,m>0\right\}\) generowany przez gramatykę \(\displaystyle G=(V_{N},V_{T},v_{0},P)\) , gdzie \(\displaystyle V_{N}=\{v_{0},v_{1}\}\) , \(\displaystyle V_{T}=\{a,b,c\}\) oraz

\(\displaystyle P= v_{0}\rightarrow v_1 v_2 , \;\; v_1 \rightarrow av_{1}b\;|ab, \;\; v_2 \rightarrow bv_2c, \;|bc\)

jest, jak łatwo sprawdzić, językiem jednoznacznym.

Mówimy, że język \(\displaystyle L\in \mathcal{L}_{2}\) jest niejednoznaczny, jeśli nie jest jednoznaczny, czyli nie istnieje gramatyka jednoznaczna generująca ten język. Przykładem języka niejednoznacznego jest

\(\displaystyle L=\left\{ a^{n}b^{n}c^{m}d^m\, :\, m,n\geqslant 1\right\} \cup \left\{ a^{n}b^{m}c^{m}d^n\, :\, m,n\geqslant 1\right\}.\)

Uzasadnienie tego faktu jest dosyć żmudne i dlatego zostało tutaj pominięte.

Zauważmy na koniec tego krótkiego omówienia problematyki jednoznaczności gramatyk, że każdy język regularny (ale nie każda gramatyka regularna) jest jednoznaczny. Jednoznaczna jest bowiem gramatyka otrzymana z automatu deterministycznego generującego ten język.

Jednoznaczny jest również język bezkontekstowy, który jest iloczynem \(\displaystyle L\cap R\) , gdzie \(\displaystyle L\in \mathcal{L}_{2}\) i jest językiem jednoznacznym, a \(\displaystyle R\in \mathcal{L}_{3}\) . Gramatyka tego języka, skonstruowana w punkcie 3 w twierdzeniu 2.1 jest jednoznaczna, co wynika stąd, że automat rozpoznający \(\displaystyle R\) jest deterministyczny.

Problemy rozstrzygalne algorytmicznie


Podobnie jak dla języków regularnych tak i w przypadku bezkontekstowych lemat o pompowaniu wykorzystuje się do uzasadnienia rozstrzygalności pewnych problemów. Dla rodziny języków bezkontekstowych mamy następujące twierdzenie.

Twierdzenie 4.1

W rodzinie języków bezkontekstowych \(\displaystyle \mathcal{L}_{2}\) następujące problemy są rozstrzygalne:

  1. problem niepustości języka, \(\displaystyle L\neq \emptyset,\)
  2. problem nieskończoności języka, \(\displaystyle card\, L=\aleph _{0},\)
  3. problem należenia słowa \(\displaystyle w\) do języka \(\displaystyle L.\)

Dowód

Aby udowodnić punkt 1, wykorzystamy następującą równoważność:

\(\displaystyle L\neq \emptyset \; \Longleftrightarrow \; \exists w\in L\, :\, |w|\leqslant N.\)

Uzasadnienie tej równoważności polega na rozkładzie słowa \(\displaystyle w\) spełniającego warunek \(\displaystyle N<|w|\) (zgodnie z oznaczeniami i tezą lematu o pompowaniu) i zastąpieniu go słowem \(\displaystyle u_{1}uu_{2}\) , które jest istotnie krótsze. Po skończonej ilości takich skracających kroków dostaniemy słowo należące do języka \(\displaystyle L\) i spełniające warunek \(\displaystyle |w|\leqslant N\) .

W uzasadnieniu punktu 2 wykorzystamy równoważność

\(\displaystyle card\, L=\aleph _{0}\Longleftrightarrow \; \exists w\in L\, :\, N<|w|\leqslant N+M,\)

gdzie \(\displaystyle M,N\) są stałymi z lematu o pompowaniu.

Przyjmując, iż język \(\displaystyle L\) jest nieskończony, wnioskujemy, że istnieją w tym języku słowa dowolnie długie. Niech \(\displaystyle w\in L\) i \(\displaystyle |w|>N\) . Jeśli \(\displaystyle w\) nie spełnia warunku \(\displaystyle |w|\leqslant N+M\) , to stosujemy lemat o pompowaniu dla \(\displaystyle i=0\) , uzyskując słowo \(\displaystyle u_{1}uu_{2}\) należące do języka i istotnie krótsze od \(\displaystyle w\) . Z warunku \(\displaystyle |w_{1}w_{2}|\leqslant |w_{1}uw_{2}|\leqslant M\) (punkt 1 tezy lematu o pompowaniu) wynika, iż różnica długości tych słów nie może być wieksza niż stała \(\displaystyle M\) . Zatem po skończonej ilości kroków uzyskujemy słowo należące do języka i spełniające żądany warunek.

Implikacja w przeciwną stronę ( \(\displaystyle \Leftarrow\) ) wynika bezpośrednio z lematu o pompowaniu. Istnieje mianowicie nieskończony zbiór słów w postaci

\(\displaystyle u_{1}w_{1}^{i}uw_{2}^{i}u_{2}\in L\)

dla \(\displaystyle i=0,1,2,....\)

Punkt 3 twierdzenia wymaga podania odpowiedniego algorytmu. Jego prezentacją i omówieniem zajmujemy się poniżej.

Algorytm CYK - przynależność słowa do języka.

Rozważmy problem przynależności słowa \(\displaystyle w\) do danego języka, generowanego przez gramatykę bezkontekstową \(\displaystyle G\). Jest to problem rozstrzygalny. Bardzo łatwo podać algorytm, wykorzystujący postać normalną Greibach. Po sprowadzeniu gramatyki \(\displaystyle G\) do postaci normalnej Greibach prawa strona każdej produkcji rozpoczyna się symbolem terminalnym i jest to jedyny symbol terminalny. Zatem jeśli \(\displaystyle w=a_1a_2...a_n\), to należy zbadać wszystkie wywody w \(\displaystyle G\), z symbolu początkowego \(\displaystyle S\), o długości dokładnie \(\displaystyle |w|\), to znaczy wywody złożone z dokładnie \(\displaystyle |w|\) kroków. Jeśli dla każdego symbolu nieterminalnego istnieje co
najwyżej \(\displaystyle k\) produkcji w gramatyce \(\displaystyle G\), w których pojawia się on po lewej stronie, to algorytm będzie działał w czasie \(\displaystyle O(k^{|w|})\). Metoda ta jest jednak bardzo nieefektywna. Czasochłonne jest też samo sprowadzenie gramatyki \(\displaystyle G\)
do postaci normalnej Greibach.

Istnieje szybszy algorytm rozwiązujący problem przynależności do języka. Jest to algorytm Cocke'a-Youngera-Kasamiego, w skrócie CYK.
Algorytm CYK działa w oparciu o ideę programowania dynamicznego . Rozważmy słowo \(\displaystyle w=a_1a_2...a_n\) oraz gramatykę \(\displaystyle G\). Niech zbiór \(\displaystyle V_i^j\) zawiera wyłącznie te symbole nieterminalne, z których można wywieść słowo \(\displaystyle a_ia_{i+1}...a_{i+j-1}\), czyli

\(\displaystyle V_i^j=\{v \in V_N: v \Rightarrow^*_G a_i a_{i+1}... a_{i+j-1} \}.\)

Mamy zatem następującą równoważność:

\(\displaystyle w \in L(G) \Leftrightarrow v_0 \in V_1^n.\)

Algorytm Cocke-Younger-Kasami - sprawdza, czy dane słowo
należy do języka generowanego przez gramatykę bezkontekstową


1 Wejście: \(\displaystyle G=(V_N, V_T, P, v_0)\), \(\displaystyle w \in V_T^*\) - gramatyka bezkontekstowa i słowo
\(\displaystyle w=a_1a_2...a_n\) o długości \(\displaystyle n\).
2 Wyjście: TAK lub NIE - odpowiedź na pytanie, czy \(\displaystyle w \in L(G)\).
3 \(\displaystyle G \leftarrow\)PostaćNormalnaChomsky'ego\(\displaystyle (G)\);
4 for \(\displaystyle i=1,...,n\) do
5 \(\displaystyle V_i^1 \leftarrow \{v \in V_N:\ (v \rightarrow a) \in P, a \in V_T\ \wedge\ a_i=a \}\);
6 end for
7 for \(\displaystyle j=2,...,n\) do
8 for \(\displaystyle i=1,...,n-j+1\) do
9 \(\displaystyle V_i^j \leftarrow\);
10 for \(\displaystyle k=1,...,j-1\) do
11 \(\displaystyle V_i^j \leftarrow V_i^j \cup \{v \in V_N:\ (v \rightarrow wy) \in P,\ w \in V_i^k,\ y \in V_{i+k}^{j-k}\}\);
12 end for
13 end for
14 end for
15 if \(\displaystyle v_0 \in V_1^n\)
16 return TAK, \(\displaystyle w \in L(G)\);
17 else
18 return NIE, \(\displaystyle w \not \in L(G)\);
19 end if

Algorytm CYK działa w czasie \(\displaystyle |w|^3\), gdzie \(\displaystyle |w|\) jest długością słowa, o którego przynależność do języka pytamy.

Przykład 4.1

Zbadamy, czy słowo \(\displaystyle w=bbaaaa\) należy do języka generowanego gramatyką:

\(\displaystyle \begin{aligned} \nonumber v & \rightarrow & wx\ |\ yz \\ \nonumber w & \rightarrow & wy\ |\ xx\ |\ a \\ \nonumber x & \rightarrow & wz\ |\ b \\ \nonumber y & \rightarrow & xy\ |\ zz\ |\ a \\ \nonumber z & \rightarrow & yy\ |\ b \end{aligned}\)

gdzie \(\displaystyle v\) jest symbolem początkowym.

Poniższa animacja ilustruje działanie algorytmu CYK.

Animacja 2