Języki, automaty i obliczenia/Wykład 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne: Różnice pomiędzy wersjami

Wersja z 12:04, 25 sie 2006

Wprowadzenie: Wprowadzimy i udowodnimy najprostszą wersję lematu o pompowaniu dla języków bezkontekstowych.
Słowa kluczowe: wyprowadzenie lewostronne i prawostronne , gramatyka jednoznaczna, język jednoznaczny

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

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

$| w_{1} u w_{2} | ⩽ M$
$w_{1} w_{2} \neq 1$
$u_{1} w_{1}^{i} u w_{2}^{i} u_{2} \in L$ dla $i = 0, 1, . . .$

Zanim przeprowadzimy dowód lematu zobaczmy jak stosuje się ten lemat do języka generowanego przez gramatykę $({v_{0}, v_{1}, v_{2}}, {a, b}, v_{0}, P)$ ,
gdzie $P : v_{0} \to v_{1} v_{2}, v_{1} \to a v_{2} b, v_{2} \to b | v_{0} b$

ANIMACJA ja-lekcja10-w-anim1-opis

Dowód

Załóżmy, bez utraty ogólności rozważań (dlaczego?), że język bezkontekstowy $L$ nie zawiera słowa pustego i jest generowany przez gramatykę $G = (V_{N}, V_{T}, v_{0}, P)$ w normalnej postaci Chomsky' ego. Rozważmy dowolne wyprowadzenie w $G$

w_{0} \mapsto w_{1} \mapsto . . . \mapsto w_{r}

o długości $r ⩾ 1$ i $w_{0} \in V_{N}$ . Niech najdłuższa ścieżka w drzewie binarnym $T$ tego wyprowadzenia ma długość $k$ (jako długość przyjmujemy tutaj liczbę wierzchołków, przez które przechodzi ścieżka). Indukcyjne ze względu na $k$ łatwo jest

uzasadnić, że

| w_{r} | ⩽ 2^{k - 1} .

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

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

Rozważmy teraz poddrzewo $T_{2}$ drzewa $T$ o wierzchołku początkowym w $s_{2}$ i niech $u$ będzie słowem określonym przez liście $T_{2}$ . Wtedy $\overline{w} = w_{1} u w_{2}$ dla pewnych $w_{1}, w_{2} \in V_{T}^{*}$ . W połączeniu z nierównością Uzupelnic lp1| uzyskujemy pierwszą własność postulowaną w lemacie. Co więcej, $w_{1} w_{2} \neq 1,$ ponieważ pierwsza produkcja wyprowadzenia $v \mapsto^{*} \overline{w}$ jest postaci $v \to v_{1} v_{2}$ dla pewnych $v_{1}, v_{2} \in V_{N}$ , a w gramatyce nie ma produkcji wymazującej. Zatem dla pewnych $u_{1}, u_{2} \in V_{T}^{*}$ jest

v_{0} \mapsto^{*} u_{1} v u_{2} \mapsto^{*} u_{1} u u_{2}

lub

v_{0} \mapsto^{*} u_{1} v u_{2} \mapsto^{*} u_{1} w_{1} v w_{2} u_{2} \mapsto^{*} u_{1} w_{1} u w_{2} u_{2} = w

lub

v_{0} \mapsto^{*} u_{1} v u_{2} \mapsto^{*} u_{1} w_{1} v w_{2} u_{2} \mapsto^{*} u_{1} w_{1}^{i} v w_{2}^{i} u_{2} \mapsto^{*} u_{1} w_{1}^{i} u w_{2}^{i} u_{2}

dla $i = 1, 2, \dots$

W konsekwencji $u_{1} w_{1}^{i} u w_{2}^{i} u_{2} \in L$ dla dowolnego $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 uzasadnienia, że pewne języki nie należą do rodziny $ℒ_{2}$ . Takie właśnie zastosowanie przedstawione jest poniżej, na przykładzie języka, o którym pó{z}niej pokażemy, że jest kontekstowy, czyli należy do rodziny języków $ℒ_{1}$ .

Przykład

Niech $L = {a^{n} b^{n} c^{n} : n ⩾ 1}$ . Przeprowadzając rozumowanie nie wprost, a więc zakładając bezkontekstowość tego języka, z lematu o pompowaniu uzyskujemy odpowiednie stałe $M, N$ . Niech $k > \frac{N}{3}$ i rozważmy słowo $x_{1} = a^{k} b^{k} c^{k}$ . Zatem istnieje rozkład $x_{1} = u_{1} w_{1} u w_{2} u_{2}$ , $w_{1} w_{2} \neq 1$ oraz $x_{i} = u_{1} w_{1}^{i} u w_{2}^{i} u_{2} \in L$ dla $i = 0, 1, . . .$ . Z postaci słów języka $L$ oraz z faktu $w_{1} w_{2} \neq 1$ wnioskujemy, że słowa $w_{1}, w_{2}$ są potęgami jednej z liter $a, b, c$ oraz że $| x_{i} | ⟶ \infty$ o ile $i ⟶ \infty$ . A to wyklucza możliwość zachowania własności określajacej język $L$ . Otrzymana sprzeczność prowadzi do wniosku, iż język ${a^{n} b^{n} c^{n} : n ⩾ 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.

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

Rodzina języków bezkontekstowych $ℒ_{2}$ jest zamknięta ze względu na następujące działania:

sumę mnogościową,
katenację i operację iteracji $*$
przecięcie (iloczyn mnogościowy) z językiem regularnym
homomorfizm

Dowód

{}

Uzupelnic dom:s|. Niech $G_{i} = (V_{N}^{i}, V_{T}, v_{0}^{i}, P_{i})$ będą gramatykami bezkontekstowymi, dla $i = 1, 2$ , takimi, że $V_{N}^{1} \cap V_{N}^{2} = \emptyset$ oraz $L_{i} = L (G_{i})$ . Język $L = L_{1} \cup L_{2}$ jest generowany przez gramatykę bezkontekstową określoną w następujący sposób:

G = (V_{N}^{1} \cup V_{N}^{2} \cup {v_{0}}, V_{T}, v_{0}, P^{1} \cup P^{2} \cup {v_{0} \to v_{0}^{1}, v_{0} \to {v_{0}}^{2}}) .

Uzupelnic dom:i|. Przy powyższych oznaczeniach, język $L = L_{1} \cdot L_{2}$ jest generowany przez gramatykę bezkontekstową:

G = (V_{N}^{1} \cup V_{N}^{2} \cup {v_{0}}, V_{T}, v_{0}, P^{1} \cup P^{2} \cup {v_{0} \to v_{0}^{1} v_{0}^{2}})

Jeśli $L = L (G)$ , dla $G = (V_{N}, V_{T}, v_{0}, P)$ gramatyki bezkontekstowej, to $L^{*} = L (\overline{G}),$ dla

gramatyki

\overline{G} = (V_{N} \cup {{\overline{v}}_{0}}, V_{T}, {\overline{v}}_{0}, P \cup {{\overline{v}}_{0} \to 1, {\overline{v}}_{0} \to {\overline{v}}_{0} v_{0}},

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

Uzupelnic dom:h|. Niech $R$ będzie dowolonym językiem rozpoznawanym przez pewien automat skończenie stanowy $𝒜 = (S, f, s_{0}, T)$ . Język ten możemy przedstawić w postaci sumy $R = ⋃_{i = 1}^{k} R_{i}$ , w której każdy język $R_{i}$ jest rozpoznawany przez automat $𝒜$ , w którym jako stan końcowy przyjmujemy $t_{i} \in T$ . Rodzina języków bezkontekstowych jest zamknięta ze względu na sumę mnogościową i oczywista jest równość $L \cap R = ⋃_{i = 1}^{k} (L \cap R_{i})$ . Wystarczy zatem udowodnić, że język $L \cap R_{i}$ jest bezkontekstowy. Załóżmy, że $T = {t}$ oraz $L$ jest językiem generowanym przez gramatykę bezkontekstową $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 $1 \notin L$ . Konstruujemy gramatykę

H = (S \times (V_{N} \cup V_{T}) \times S, V_{T}, (s_{0}, v_{0}, t), P_{H}),

dla której $P_{H}$ zawiera następujące produkcje

$(s_{1}, v_{1}, s_{2}) \to (s_{1}, v_{2}, s_{3}) (s_{3}, v_{3}, s_{2})$ dla $s_{i} \in S$ , $v_{i} \in V_{N}$ jeśli $v_{1} \to v_{2} v_{3} \in P$
$(s_{1}, v_{1}, s_{2}) \to (s_{1}, a, s_{2})$ dla $s_{i} \in S$ , $a \in V_{T}$ jeśli $v_{1} \to a \in P$
$(s_{1}, a, s_{2}) \to a$ dla $s_{i} \in S$ , $a \in V_{T}$ jeśli $f (s_{1}, a) = s_{2} .$

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

Uzupelnic dom:j|. Niech $h : A^{*} ⟶ B^{*}$ oznacza dowolny homomorfizm, a $L \subset A^{*}$ językiem bezkontekstowym generowanym przez gramatykę $G = (V_{N}, A, v_{0}, P)$ . Rozszerzamy homomorfizm $h$ do wolnych monoidów $(A \cup V_{N})^{*}$ i $(B \cup V_{N})^{*}$ , przyjmując, że $h$ na zbiorze $V_{N}$ jest równe identyczności. Łatwo zauważyć, że język $h (L)$ jest generowany przez gramatykę bezkontekstową $G = (V_{N}, B, v_{0}, P_{h})$ , w której

P_{h} = {v \to h (w) : v \to w \in P} .

♢

Z równości $L ∖ R = L \cap \overline{R}$ , zamkniętości klasy $ℒ_{3}$ ze względu na uzupełnienie oraz z punktu Uzupelnic dom:h| udowodnionego powyżej twierdzenia wynika następujący wniosek.

Wniosek

Niech $L \subset A^{*}$ będzie dowolonym językiem bezkontekstowym, a $R \subset A^{*}$ regularnym. Wtedy $L ∖ 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

Rodzina języków bezkontekstowych $ℒ_{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

Rodzina języków bezkontekstowych $ℒ_{2}$ nie jest zamknięta ze względu na

iloczyn mnogościowy
uzupełnienie

Dowód

Dla $i = 1, 2$ niech $G_{i} = ({v_{0}, v_{1}}, {a, b, c}, v_{0}, P_{i})$ będą gramatykami o następujących zbiorach praw:

\begin{array}{l} P_{1} = {v_{0} \to v_{0} c, v_{0} \to v_{1} c, v_{1} \to a b, v_{1} \to a v_{1} b} \\ P_{2} = {v_{0} \to a v_{0}, v_{0} \to a v_{1}, v_{1} \to b c, v_{1} \to b v_{1} c} . \end{array}

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

L (G_{1}) = {a^{n} b^{n} c^{m} : n, m ⩾ 1} \in ℒ_{2}

L (G_{2}) = {a^{n} b^{m} c^{m} : n, m ⩾ 1} \in ℒ_{2} .

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

L (G_{1}) \cap L (G_{2}) = {a^{n} b^{n} c^{n} : n ⩾ 1} \notin ℒ_{2}

jest językiem istotnie kontekstowym.

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

♢

3. 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 nieporzą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

Niech $G = (V_{N}, V_{T}, v_{0}, P)$ będzie gramatyką bezkontekstową. Lewostronnym (prawostronnym) wyprowadzeniem słowa $w \in {V_{T}}^{*}$ w gramatyce $G$ nazywamy

wyprowadzenie

v_{0} \mapsto w_{1} \mapsto \dots . . \mapsto w_{n} = w

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

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

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

Gramatyka bezkontekstowa $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 $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 $L \subset A^{*}$ , że $L \subset w_{1}^{*} . . . w_{n}^{*}$ dla pewnych słów $w_{1}, . . ., w_{n} \in A^{*}$ .

Przykład

Język ${a^{n} b^{n + m} c^{m} : n, m > 0}$ generowany przez gramatykę $G = (V_{N}, V_{T}, v_{0}, P)$ , gdzie $V_{N} = {v_{0}, v_{1}}$ , $V_{T} = {a, b, c}$ oraz
$P = v_{0} \to v_{1} v_{2}, v_{1} \to a v_{1} b | a b, v_{2} \to b v_{2} c, | b c$
jest, jak łatwo sprawdzić, językiem jednoznacznym.

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

L = {a^{n} b^{n} c^{m} d^{m} : m, n ⩾ 1} \cup {a^{n} b^{m} c^{m} d^{n} : m, n ⩾ 1} .

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 $L \cap R$ , gdzie $L \in ℒ_{2}$ i jest językiem jednoznacznym, a $R \in ℒ_{3}$ . Gramatyka tego języka, skonstruowana w punkcie Uzupelnic p1| w twierdzeniu Uzupelnic tw 2| jest jednoznaczna, co wynika stąd, że automat rozpoznający $R$ jest deterministyczny.

4. Problemy rozstrzygalne algorytmicznie

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

Twierdzenie

W rodzinie j{e}zyków bezkontekstowych $ℒ_{2}$ nast{e}puj{a}ce problemy s{a} rozstrzygalne:

problem niepustości języka, $L \neq \emptyset$
problem nieskończoności języka, $c a r d L = ℵ_{0}$
problem należenia słowa $w$ do języka $L$

Dowód

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

L \neq \emptyset ⟺ \exists w \in L : | w | ⩽ N,

Uzasadnienie tej równoważności polega

na rozk{}adzie s{}owa $w$ spe{}niaj{a}cego warunek $N < | w |$ (zgodnie z oznaczeniami i tezą lematu o pompowaniu) i zastąpieniu go s{}owem $u_{1} u u_{2}$ , które jest istotnie krótsze. Po sko{n}czonej ilo{s}ci takich skracających kroków dostaniemy s{}owo nale{z}{a}ce do j{e}zyka $L$ i spe{}niaj{a}ce warunek $| w | ⩽ N$ .

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

c a r d L = ℵ_{0} ⟺ \exists w \in L : N < | w | ⩽ N + M,

gdzie $M, N$ są stałymi z lematu o pompowaniu.

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

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

u_{1} w_{1}^{i} u w_{2}^{i} u_{2} \in L

dla $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 $w$ do danego języka, generowanego przez gramatykę bezkontekstową $G$ . Jest to problem rozstrzygalny. Bardzo łatwo podać algorytm, wykorzystujący postać normalną Greibach. Po sprowadzeniu gramatyki $G$ do postaci normalnej Greibach prawa strona każdej produkcji rozpoczyna się symbolem terminalnym i jest to jedyny symbol terminalny. Zatem, jeśli $w = a_{1} a_{2} . . . a_{n}$ , to należy zbadać wszystkie wywody w $G$ , z symbolu początkowego $S$ , o długości dokładnie $| w |$ , to znaczy wywody złożone z dokładnie $| w |$ kroków. Jeśli dla każdego symbolu nieterminalnego istnieje co najwyżej $k$ produkcji w gramatyce $G$ , w których pojawia się on po lewej stronie, to algorytm będzie działał w czasie $O (k^{| w |})$ . Metoda ta jest jednak bardzo nieefektywna. Czasochłonne jest też samo sprowadzenie gramatyki $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 $w = a_{1} a_{2} . . . a_{n}$ oraz gramatykę $G$ . Niech zbiór $V_{i}^{j}$ zawiera wyłącznie te symbole nieterminalne, z których można wywieść słowo $a_{i} a_{i + 1} . . . a_{i + j - 1}$ , czyli

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ść:

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: $G = (V_{N}, V_{T}, P, v_{0})$ , $w \in V_{T}^{*}$ - gramatyka bezkontekstowa i słowo $w = a_{1} a_{2} . . . a_{n}$ o długości $n$

Wyjście: TAK lub NIE - odpowiedź na pytanie, czy $w \in L (G)$ .

$G \leftarrow$ PostaćNormalnaChomsky'ego $(G)$ ;

for $i = 1, . . ., n V_{i}^{1} \leftarrow {v \in V_{N} : (v \to a) \in P, a \in V_{T} \land a_{i} = a}$ ;

endfor

for $j = 2, . . ., n$

for $i = 1, . . ., n - j + 1 V_{i}^{j} \leftarrow$ ;

for $k = 1, . . ., j - 1 V_{i}^{j} \leftarrow V_{i}^{j} \cup {v \in V_{N} : (v \to w y) \in P, w \in V_{i}^{k}, y \in V_{i + k}^{j - k}}$ ;

endfor

if $v_{0} \in V_{1}^{n}$

return TAK, $w \in L (G)$ ;

else

return NIE, $w \in̸ L (G)$ ;

endif

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

Przykład

Zbadamy, czy słowo $w = b b a a a a$ należy do języka generowanego gramatyką:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \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 \endaligned}

gdzie $v$ jest symbolem początkowym.

Poniższa animacja ilustruje działanie algorytmu CYK.

ANIMACJA ja-lekcja10-w-anim2.jpg. Opis animacji w pliku ja-lekcja10-w-anim2-opis.

Języki, automaty i obliczenia/Wykład 10: Lemat o pompowaniu dla języków bezkontekstowych. Własności języków bezkontekstowych. Problemy rozstrzygalne: Różnice pomiędzy wersjami

Wersja z 12:04, 25 sie 2006

Spis treści

1. Lemat o pompowaniu

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

3. Jednoznaczność języków bezkontekstowych

4. Problemy rozstrzygalne algorytmicznie

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-{theor}{TWIERDZENIE}[section]
-{rem}{UWAGA}[section]
-{corol}{WNIOSEK}[section]
-{fact}{FAKT}[section]
-{ex}{PRZYKŁAD}[section]
-{defin}{DEFINICJA}[section]
-{lem}{LEMAT}[section]
-{prf}{DOWÓD}
-{Automat ze stosem.Gramatyki bezkontekstowe i automaty ze stosem.}
-==Automat ze stosem==
 ; Wprowadzenie
-:   W tym wykładzie
+:  Wprowadzimy  i udowodnimy najprostszą wersję lematu o pompowaniu dla języków bezkontekstowych.
-określimy automat ze stosem rozpoznający języki
-bezkontekstowe.  Wprowadzimy
-dwie definicje rozpoznawania języków
-przez automat ze stosem oraz omówimy ważną podklasę języków bezkontekstowych,
-mianowicie  języków rozpoznawanych przez deterministyczne automaty ze stosem.
-Uzasadnimy też fakt, iż rodzina języków rozpoznawana przez automaty ze stosem pokrywa się
-z rodziną jezyków bezkontekstowych.
 ; Słowa kluczowe
-:   automat ze stosem, konfiguracja, deterministyczny automat
+: wyprowadzenie  lewostronne i prawostronne , gramatyka jednoznaczna, język jednoznaczny
-ze stosem, rodzina
-jezyków rozpoznawanych przez automaty ze stosem.
-Automaty ze stosem  to systemy rozpoznające języki bezkontekstowe. Ich działanie jest nieco
+==1. Lemat o pompowaniu==
-bardziej skomplikowane niż działanie automatu skończenie stanowego. Poza możliwością
-zmiany stanu pod wpływem czytanego symbolu
-umieszczonego na taśmie wejściowej automat ten  posiada także taśmę stosu, na którą
-może wpisywać
-słowa, jak i odczytywać pojedynczy symbol znajdujący się na wierzchu stosu.
-{{definicja|||
+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.
-Automatem ze stosem nad alfabetem  <math>\displaystyle A  </math>  nazywamy
+{{lemat|1||
-system  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,f,s_{0},z_{0},Q_{F})  </math> , w którym<br>
+(o pompowaniu) Dla dowolnego języka bezkontekstowego <math>\displaystyle L \subset A^*</math> istnieją liczby
+naturalne <math>\displaystyle N,M \geqslant 1</math> takie, że każde słowo <math>\displaystyle w \in L</math> o długości <math>\displaystyle |w| > N</math> można
+przedstawić w formie <math>\displaystyle w=u_1w_1uw_2u_2</math>, gdzie  <math>\displaystyle w_{1,}w_{2},v_{1},v_{2},u\in A^{*}  </math> ,
+oraz
+# <math>\displaystyle |w_1uw_2| \leqslant M</math>
+# <math>\displaystyle w_1w_2 \neq 1</math>
+# <math>\displaystyle u_1w_1^iuw_2^iu_2 \in L</math> dla <math>\displaystyle i=0,1,...</math>
-<math>\displaystyle A  </math>  - jest alfabetem,
+}}
-<math>\displaystyle A_{S}  </math>  - jest dowolnym skończonym i niepustym zbiorem zwanym alfabetem
+Zanim przeprowadzimy  dowód lematu zobaczmy jak stosuje się ten lemat do języka  generowanego
-stosu (niekoniecznie rozłącznym z  <math>\displaystyle A  </math> ),
+przez gramatykę <math>\displaystyle (\{v_0,v_1,v_2 \},\{a,b\},v_0,P)</math>, <br>
+gdzie <math>\displaystyle P: v_0 \rightarrow v_1v_2, \;v_1 \rightarrow av_2 b  , v_2 \rightarrow b\;|\;v_0b</math><br>
-<math>\displaystyle Q  </math>  - jest dowolnym, skończonym i niepustym zbiorem zwanym zbiorem
+<font color=red>ANIMACJA ja-lekcja10-w-anim1-opis</font>
-stanów,
-<math>\displaystyle f:A_{S}\times Q\times (A\cup \left\{ 1\right\} )\longrightarrow \mathcal{P}_{sk}(A_{S}^{*}\times Q)  </math>
+{{dowod|||
-jest funkcją przejść, której wartościami są skończone podzbiory
+Załóżmy, bez utraty ogólności rozważań (dlaczego?), że język bezkontekstowy <math>\displaystyle L</math>
-<math>\displaystyle A_{S}^{*}\times Q  </math>  (także zbiór pusty),
+nie zawiera słowa pustego i jest
+generowany  przez gramatykę <math>\displaystyle G=(V_N,V_T,v_0,P)</math>
+w&nbsp;normalnej postaci Chomsky' ego.
+Rozważmy dowolne wyprowadzenie w <math>\displaystyle G</math>
+<center><math>\displaystyle w_0 \mapsto w_1 \mapsto ... \mapsto w_r</math></center>
-<math>\displaystyle q_{0}\in Q  </math>  jest stanem początkowym,
+o długości <math>\displaystyle r \geqslant 1</math> i <math>\displaystyle w_0 \in V_N</math>. Niech  najdłuższa ścieżka
+w drzewie binarnym <math>\displaystyle T</math> tego wyprowadzenia ma długość <math>\displaystyle k</math>
+(jako długość przyjmujemy tutaj liczbę
+wierzchołków, przez które przechodzi ścieżka). Indukcyjne ze względu na  <math>\displaystyle k  </math>   łatwo jest
+uzasadnić, że <center><math>\displaystyle |w_r| \leqslant 2^{k-1}.</math></center>
+Załóżmy teraz, że zbiór <math>\displaystyle V_N</math> ma <math>\displaystyle p</math> elementów i
+przyjmijmy <math>\displaystyle N=2^p</math> oraz <math>\displaystyle M=2^{p+1}</math>. Niech <math>\displaystyle w \in L(G)</math> będzie słowem, którego długość jest
+większa od <math>\displaystyle N</math>.
+Zatem najdłuższa ścieżka <math>\displaystyle S</math> w drzewie wyprowadzenia <math>\displaystyle T</math> będącego
+wyprowadzeniem słowa <math>\displaystyle w</math> w
+gramatyce <math>\displaystyle G</math> ma długość co najmniej <math>\displaystyle p+2</math>. A więc przechodzi przez co najmniej <math>\displaystyle p+2</math>
+wierzchołków. Stąd, że
+wierzchołki maksymalne drzewa wyprowadzenia mają etykiety terminalne wnioskujemy,
+że w <math>\displaystyle S</math> występują dwa różne
+wierzchołki <math>\displaystyle s_1, s_2</math> etykietowane przez ten sam symbol nieterminalny <math>\displaystyle v</math>.
+Przyjmijmy, że wierzchołek <math>\displaystyle s_1</math> jest
+bliższy wierzchołka początkowego drzewa wyprowadzenia niż <math>\displaystyle s_2</math>.
+Wierzchołki <math>\displaystyle s_1, s_2</math> można tak dobrać,
+aby podścieżka ścieżki <math>\displaystyle S</math> o początku w wierzchołku <math>\displaystyle s_1</math> miała długość równą
+co najwyżej <math>\displaystyle p+2</math>.
+Zauważmy teraz, że żadna ścieżka poddrzewa
+<math>\displaystyle T_1</math>, którego wierzchołkiem początkowym jest <math>\displaystyle s_1</math>,
+nie ma długości większej niż <math>\displaystyle p+2</math>. Jeśli więc <math>\displaystyle \overline w</math> jest słowem
+określonym przez liście <math>\displaystyle T_1</math>,
+to
-<math>\displaystyle z_{0}\in A_{S}  </math>  symbolem początkowym stosu,
+<center><math>\displaystyle
+|\overline{w}|\leqslant 2^{(p+2)-1}=M.
+</math></center>
-<math>\displaystyle Q_{F}\subset Q  </math>  zbiorem stanów końcowych.
+Rozważmy teraz poddrzewo <math>\displaystyle T_2</math> drzewa <math>\displaystyle T</math> o wierzchołku początkowym w <math>\displaystyle s_2</math>
+i niech <math>\displaystyle u</math> będzie słowem określonym
+przez liście <math>\displaystyle T_2</math>. Wtedy <math>\displaystyle \overline w= w_1uw_2</math> dla pewnych <math>\displaystyle w_1, w_2 \in V_T^*</math>.
+W połączeniu z nierównością [[##lp1|Uzupelnic lp1|]]
+uzyskujemy pierwszą własność postulowaną w lemacie. Co więcej, <math>\displaystyle w_1w_2 \neq 1,</math>
+ponieważ pierwsza produkcja wyprowadzenia
+<math>\displaystyle v\mapsto^{*}\overline{w}  </math>  jest postaci <math>\displaystyle v \rightarrow v_1v_2</math> dla pewnych
+<math>\displaystyle v_{1},\, v_{2}\in V_{N}  </math> , a w gramatyce nie
+ma produkcji wymazującej. Zatem dla pewnych <math>\displaystyle u_1, u_2 \in V^*_T</math> jest
-}}
+<center><math>\displaystyle v_{0}\mapsto^{*}u_{1}vu_{2}\mapsto^{*}u_{1}uu_{2}</math></center>
-Badając działanie automatu ze stosem wygodniej jest zamiast funkcji przejść  <math>\displaystyle f  </math>
+lub <center><math>\displaystyle v_0 \mapsto^* u_1vu_2 \mapsto^* u_1w_1vw_2u_2 \mapsto^* u_1 w_1 uw_2 u_2 = w</math></center>
-rozważać skończoną relację
+lub
-<math>\displaystyle P\subset (A_{S}\times Q\times (A\cup \left\{ 1\right\} ))\times (A_{S}^{*}\times Q)  </math>
-zwaną relacją przejść. Elementy tej relacji nazywane są prawami. Relacja  <math>\displaystyle P  </math>
-jest zatem skończonym zbiorem praw o następującej postaci:
-# <math>\displaystyle zq_i \longrightarrow uq_j </math> dla <math>\displaystyle z \in A_S, \;\; u \in A_S^*, \;\; q_i ,q_j \in Q</math>,
-# <math>\displaystyle zq_i a \longrightarrow uq_j </math> dla <math>\displaystyle z \in A_S, \;\; u \in A_S^*, \;\; a \in A, \;\;q_i ,q_j \in Q</math>.
-Często, używając relacji przejść, oznaczamy automat ze stosem jako układ
+<center><math>\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}</math></center>
-<center><math>\displaystyle  \mathcal{AS}=(A,A_{S},Q,P,s_{0},z_{0},Q_{F}) .</math></center>
-Prawo  <math>\displaystyle zq_{i}a\longrightarrow uq_{j}  </math>  będziemy
+dla  <math>\displaystyle i=1,2,\ldots   </math>
-reprezentować grafem<br>
-rys1   ja-lekcja11-w-rys1 <br>
+W konsekwencji <math>\displaystyle u_1w_1^iuw_2^iu_2 \in L</math> dla dowolnego <math>\displaystyle i=0,1,...</math>. Lemat zatem został
-Napis <math>\displaystyle z/u</math> oznacza, iż symbol <math>\displaystyle z</math> pobrany ze stosu wymieniany jest na słowo <math>\displaystyle u</math>
+udowodniony.
-utworzone nad alfabetem stosu <math>\displaystyle A_S</math>.
-Natomiast prawo  <math>\displaystyle zq_{i}\rightarrow uq_{j}  </math>  interpretowane jest graficznie  jako:<br>
+<math>\displaystyle \diamondsuit</math>   }}
-rys2   ja-lekcja11-w-rys2 <br>
+Analogicznie jak w przypadku języków regularnych, lemat o pompowaniu dla języków bezkontekstowych
+stosuje się najczęściej do uzasadnienia,
+że pewne języki nie należą do rodziny  <math>\displaystyle \mathcal{L}_{2}  </math> .
+Takie właśnie zastosowanie przedstawione jest poniżej, na przykładzie
+języka, o którym pó{z}niej pokażemy, że jest kontekstowy, czyli należy do rodziny
+języków  <math>\displaystyle \mathcal{L}_{1}  </math> .
-Działanie automatu ze stosem  <math>\displaystyle \mathcal{AS}  </math>  zależne jest, jak wspomnieliśmy
+{{przyklad|||
-na wstepie wykładu, nie tylko od czytanego
+Niech <math>\displaystyle L=\{a^nb^nc^n : n \geqslant 1 \}</math>. Przeprowadzając rozumowanie nie wprost, a więc
-przez automat słowa, ale
+zakładając  bezkontekstowość
-także od symbolu znajdującego się na wierzchu stosu. Poniżej przedstawiamy graficznie<br>
+tego języka, z lematu o pompowaniu uzyskujemy odpowiednie stałe <math>\displaystyle M, N</math>.
-te zależności.
+Niech <math>\displaystyle k > \frac{N}{3}</math> i rozważmy słowo <math>\displaystyle x_1=a^kb^kc^k</math>. Zatem
+istnieje rozkład <math>\displaystyle x_1=u_1w_1uw_2u_2</math>, <math>\displaystyle w_1w_2 \neq 1</math> oraz <math>\displaystyle x_i=u_1w_1^iuw_2^iu_2 \in L</math>
+dla <math>\displaystyle i=0,1,...</math> .
+Z postaci słów języka <math>\displaystyle L</math> oraz z faktu <math>\displaystyle w_1w_2 \neq 1</math> wnioskujemy, że słowa <math>\displaystyle w_1, w_2</math>
+są potęgami
+jednej z liter <math>\displaystyle a,b,c</math> oraz że <math>\displaystyle |x_i| \longrightarrow \infty</math> o ile <math>\displaystyle i \longrightarrow \infty</math>.
+A to wyklucza możliwość
+zachowania własności określajacej  język <math>\displaystyle L</math>. Otrzymana sprzeczność prowadzi do wniosku, iż
+język <math>\displaystyle \{a^nb^nc^n : n \geqslant 1 \}</math> nie jest bezkontekstowy.
-Rysunek 3    ja-lekcja11-w-rys3 <br>
+}}
-Prawo  <math>\displaystyle zq_{i}a\longrightarrow uq_{j}  </math>  dla słowa  <math>\displaystyle u=z_{1}\ldots z_{m}  </math>
+Lemat o pompowaniu wykorzystywany bywa również w dowodach rozstrzygalności pewnych
-określające działanie automatu  <math>\displaystyle \mathcal{AS}  </math>  interpretujemy w ten sposób,
+problemów w rodzinie języków rozpoznawalnych. Zagadnieniem tym zajmiemy się w
-że automat będąc w stanie  <math>\displaystyle q_{i}  </math>  po przeczytaniu litery  <math>\displaystyle a  </math>
+dalszej części tego wykładu.
-(ze słowa wejściowego) i symbolu  <math>\displaystyle z  </math>  ze stosu zmienia stan na  <math>\displaystyle q_{j}  </math>
-oraz wpisuje na stos słowo  <math>\displaystyle u  </math>  w ten sposób, że ostatnia litera tego słowa,
-symbol  <math>\displaystyle z_{m}  </math> , jest na wierzchu stosu. Ten właśnie symbol będzie pobrany
-ze stosu przy kolejnym "ruchu" automatu, zgodnie z zasadą ''last in,
-first out. ''  Ilustruje tę zasadę animacja, która
-zamieszczona w dalszej części tego wykładu.
-{}
+==2. Własności rodziny języków bezkontekstowych==
-Dla precyzyjnego opisu działania automatu ze stosem wprowadza się pojęcie konfiguracji
+Przedstawimy teraz podstawowe własności rodziny języków bezkontekstowych
-automatu, poprzedzając to pojęcie określeniem konfiguracji wewnętrznej.
+związane z zamkniętością ze względu na działania oraz
+z&nbsp;problemami jednoznaczności.
-{{definicja|||
+{{twierdzenie|||
-Konfiguracją wewnętrzną automatu ze stosem  <math>\displaystyle AS  </math>  nazywamy dowolną parę
-<math>\displaystyle (u,q)\in A_{S}^{*}\times Q  </math>  taką, że  <math>\displaystyle q  </math>  jest stanem, w którym automat
-znajduje się aktualnie, a  <math>\displaystyle u  </math>  słowem zapisanym na stosie tak, że litera
-będaca na wierzchu stosu jest ostatnią literą tego słowa.
-Konfiguracją automatu ze stosem  <math>\displaystyle AS  </math>
-nazywamy trójkę
-<center><math>\displaystyle (u,q,w)\in A_{S}^{*}\times Q\times A^{*}</math></center>
-gdzie  <math>\displaystyle (u,q)  </math>  jest konfiguracją wewnętrzną, a  <math>\displaystyle w  </math>
+Rodzina języków bezkontekstowych  <math>\displaystyle \mathcal{L}_{2}  </math>  jest zamknięta ze względu
-słowem wejściowym.
+na następujące działania:
+#  sumę mnogościową,
+#  katenację i operację iteracji <math>\displaystyle  *</math>
+#   przecięcie (iloczyn mnogościowy) z językiem regularnym
+#  homomorfizm
 }}
-Wprowadzone pojęcia wykorzystamy do określenia działania automatu ze stosem
+{{dowod|||
-dla dowolnych słów wejściowych i dowolnych słów znajdujących się na stosie.
+{}
-W tym celu rozszerzymy odpowiednio relację przejść  <math>\displaystyle P  </math> , określając ją na zbiorze
-konfiguracji
-i&nbsp;oznaczając symbolem  <math>\displaystyle |\! \! \! \Longrightarrow   </math> . Przyjmujemy dla dowolnych
-słów  <math>\displaystyle u_{1},u_{2}\in A_{S}^{*}  </math>  i litery  <math>\displaystyle z\in A_{S}  </math> , dla dowolnego
-słowa  <math>\displaystyle w\in A^{*}  </math>  i  <math>\displaystyle a\in A\cup \left\{ 1\right\}   </math>  oraz dla dowolnych
-stanów  <math>\displaystyle q_{1},q_{2}\in Q  </math> , że zachodzi relacja
-<center><math>\displaystyle (u_{1}z,q_{1},aw)\, |\! \! \! \Longrightarrow (u_{1}u_{2},q_{2},w)</math></center>
+[[##dom:s|Uzupelnic dom:s|]].  Niech <math>\displaystyle G_i = (V^i_N ,V_T,v^i_0,P_i)</math> będą gramatykami bezkontekstowymi,
+dla <math>\displaystyle i=1,2</math>, takimi,
+że <math>\displaystyle V^1_N \cap V^2_N = \emptyset</math> oraz <math>\displaystyle  L_i = L(G_i)</math>. Język <math>\displaystyle L = L_1 \cup L_2</math> jest
+generowany
+przez gramatykę bezkontekstową określoną w następujący sposób:
+<center><math>\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 \}).</math></center>
-wtedy i tylko wtedy, gdy  <math>\displaystyle zq_{1}a\longrightarrow u_{2}q_{2}\in P  </math> .
+[[##dom:i|Uzupelnic dom:i|]]. Przy powyższych oznaczeniach, język <math>\displaystyle L = L_1 \cdot L_2</math> jest generowany przez
+gramatykę bezkontekstową:
+<center><math>\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 \})</math></center>
-Zwrotne i przechodnie domknięcie tej relacji nazywamy przejściem lub poprawnym obliczeniem
+Jeśli <math>\displaystyle L = L(G)</math>, dla <math>\displaystyle G = (V_N ,V_T,v_0,P)</math> gramatyki bezkontekstowej, to
-automatu  <math>\displaystyle AS  </math>  i oznaczamy symbolem  <math>\displaystyle |\! \! \! \Longrightarrow ^{*}  </math> .
+<math>\displaystyle L^* = L(\overline{G}),</math> dla
+gramatyki <center><math>\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 \},</math></center>
-Dla dowolnego słowa  <math>\displaystyle w\in A^{*}  </math>  przyjmujemy oznaczenie  <math>\displaystyle (u,q)\, \mid \! \Longrightarrow ^{w}\, (u_{1},q_{1})  </math> ,
+która jest również gramatyką bezkontekstową.
-jeśli ma miejsce  <math>\displaystyle (u,q,w)|\! \! \! \Longrightarrow ^{*}(u_{1},q_{1},1)  </math> . Prawdziwa
-jest wówczas następująca równość:
-<center><math>\displaystyle \begin{array} [b]{c}
+[[##dom:h|Uzupelnic dom:h|]]. Niech <math>\displaystyle R</math> będzie dowolonym językiem rozpoznawanym przez pewien automat skończenie
-|\! \! \! \Longrightarrow ^{w_{1}}\circ
+stanowy  <math>\displaystyle \mathcal{A}  \displaystyle =(S,f,s_0,T)</math>. Język ten możemy przedstawić w postaci sumy
-\end{array} \begin{array} [b]{c}
+<math>\displaystyle R=\bigcup_{i=1}^k R_i</math>, w której
-|\! \! \! \Longrightarrow ^{w_{2}}\: =
+każdy język <math>\displaystyle R_i</math> jest rozpoznawany przez automat  <math>\displaystyle \mathcal{A}  </math> , w którym jako stan
-\end{array} \begin{array} [b]{c}
+końcowy przyjmujemy <math>\displaystyle t_i \in T</math>. Rodzina
-|\! \! \! \Longrightarrow ^{w_{1}w_{2}}
+języków bezkontekstowych jest zamknięta ze względu na sumę mnogościową i
-\end{array} </math></center>
+oczywista jest równość <math>\displaystyle L \cap R= \bigcup _{i=1}^k (L \cap R_i)</math>.
+Wystarczy zatem udowodnić, że język <math>\displaystyle L \cap R_i</math> jest
+bezkontekstowy. Załóżmy, że <math>\displaystyle T=\{t \}</math> oraz <math>\displaystyle L</math> jest językiem generowanym przez gramatykę
+bezkontekstową <math>\displaystyle G = (V_N ,V_T,v_0,P)</math> w normalnej postaci Chomsky' ego.
+Bez utraty ogólności rozważań
+można także założyć, że  <math>\displaystyle 1\notin L  </math> . Konstruujemy gramatykę
+<center><math>\displaystyle H=(S \times (V_N \cup V_T) \times S,V_T,(s_0,v_0,t),P_H),</math></center>
+dla której <math>\displaystyle P_H</math>
+zawiera następujące produkcje
+* <math>\displaystyle (s_1,v_1,s_2) \rightarrow (s_1,v_2,s_3)(s_3,v_3,s_2)</math> dla <math>\displaystyle s_i \in S</math>, <math>\displaystyle v_i \in V_N</math> jeśli <math>\displaystyle v_1\rightarrow v_2v_3 \in P</math>
+* <math>\displaystyle (s_1,v_1,s_2) \rightarrow (s_1,a,s_2)</math> dla <math>\displaystyle s_i \in S</math>, <math>\displaystyle a \in V_T</math> jeśli <math>\displaystyle v_1\rightarrow a \in P</math>
+* <math>\displaystyle (s_1,a,s_2)\rightarrow a</math> dla <math>\displaystyle s_i \in S</math>, <math>\displaystyle a \in V_T</math> jeśli <math>\displaystyle f(s_1,a)=s_2.</math>
-Mówimy, że konfiguracja wewnętrzna  <math>\displaystyle (u,q)  </math>  automatu ze stosem
+Bezpośrednio z konstrukcji wynika, że gramatyka <math>\displaystyle H</math> jest bezkontekstowa.
-<math>\displaystyle AS  </math>  jest osiągalna z konfiguracji wewnętrznej  <math>\displaystyle (u_{1},q_{1})  </math>
+Łatwo również zauważyć, że język
-jeśli istnieje takie słowo  <math>\displaystyle w\in A^{*}  </math> , że
+generowany przez gramatykę <math>\displaystyle H</math> jest równy <math>\displaystyle L \cap R</math>.
-<center><math>\displaystyle (u_{1},q_{1})\, \mid \! \Longrightarrow ^{w}\, (u,q).</math></center>
+[[##dom:j|Uzupelnic dom:j|]]. Niech <math>\displaystyle h: A^* \longrightarrow B^*</math> oznacza dowolny homomorfizm, a
+<math>\displaystyle L \subset A^*</math> językiem bezkontekstowym
+generowanym przez gramatykę <math>\displaystyle G = (V_N ,A,v_0,P)</math>. Rozszerzamy homomorfizm <math>\displaystyle h</math> do wolnych
+monoidów
+<math>\displaystyle (A \cup V_N)^*</math> i <math>\displaystyle (B \cup V_N)^*</math>, przyjmując, że <math>\displaystyle h</math> na zbiorze  <math>\displaystyle V_N</math> jest równe
+identyczności. Łatwo zauważyć, że język <math>\displaystyle h(L)</math> jest generowany przez gramatykę
+bezkontekstową <math>\displaystyle G = (V_N, B, v_0, P_h)</math>, w której
+<center><math>\displaystyle P_h=\{ v \rightarrow h(w) : v \rightarrow w \in P \}.</math></center>
-Zdefiniujemy teraz język rozpoznawany przez automat ze stosem. W literaturze spotkać
+<math>\displaystyle \diamondsuit</math>   }}
-można kilka równoważnych definicji rozpoznawania. W naszym wykładzie wprowadzimy dwie,
-używane najczęściej:
-# rozpoznawanie poprzez stany końcowe (wyróżniony zbiór stanów końcowych
-<math>\displaystyle Q_{F}  </math> ),
-# rozpoznawanie poprzez pusty stos.
-{{definicja|||
-Niech  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,P,s_{0},z_{0},Q_{F})  </math>  będzie automatem ze stosem.
-Językiem rozpoznawanym przez automat  <math>\displaystyle  \mathcal{AS}</math> poprzez
-stany końcowe nazywamy zbiór
-<center><math>\displaystyle L_{F}(\mathcal{AS})=\left\{ w\in A^{*}\; : \; (z_{0},q_{0})\; \mid \! \Longrightarrow ^{w}\, (u,q_{F}),\; : u\in A_{S}^{*}, \; q_{F}\in Q_{F}\right\}. </math></center>
-Językiem rozpoznawanym przez automat <math>\displaystyle \mathcal{AS}</math> poprzez pusty stos nazywamy zbiór
+Z równości  <math>\displaystyle L\setminus R=L\cap \overline{R}  </math> ,
+zamkniętości klasy  <math>\displaystyle \mathcal{L}_{3}  </math>  ze względu na uzupełnienie
+oraz z punktu [[##dom:h|Uzupelnic dom:h|]] udowodnionego powyżej twierdzenia wynika następujący
+wniosek.
-<center><math>\displaystyle L_{e}(\mathcal{AS})=\left\{ w\in A^{*}\, :\, (z_{0},q_{0})\, \mid \! \Longrightarrow ^{w}\, (1,q),\, q\in Q\right\} .</math></center>
+{{wniosek|||
+Niech <math>\displaystyle L \subset A^*</math> będzie dowolonym językiem bezkontekstowym, a
+<math>\displaystyle R \subset A^*</math> regularnym. Wtedy <math>\displaystyle L \setminus R</math> jest
+językiem bezkontekstowym.
 }}
-Używając drugiego określenia rozpoznawania, w definicji automatu
+Bez dowodu podajemy dwie dalsze własności związane z zamkniętością rodziny
-ze stosem pomija się zbiór stanów końcowych  <math>\displaystyle Q_{F}  </math> .
+języków bezkontekstowych.
-{{przyklad|||
+{{fakt|||
-Poniższa animacja  ilustruje działanie automatu ze stosem.
+Rodzina języków bezkontekstowych  <math>\displaystyle \mathcal{L}_{2}  </math>  jest zamknięta ze
-Przedstawiony grafem automat ze stosem
+względu na podstawienie
-<math>\displaystyle  \mathcal{AS}=(A,A_{S},\{q_0,q_F\},P,q_{0},z_{0},\{q_{F}\})</math>,  w&nbsp;którym
+regularne i przeciwobraz przez homomorfizm.
-alfabet stosu  <math>\displaystyle A_{S}=\{z_{0},a,b\}  </math>  rozpoznaje język bezkontekstowy
-<center><math>\displaystyle L( \mathcal{AS})= \{w \in \{a,b\}^* \;\; : \;\; \#_a w = \#_b w \}.</math></center>
-ANIMACJA ja-lekcja11-w-anim1.ppt
-Zauważmy, że automat ten rozpoznaje ten sam język zarówno zarówno
-przez stany końcowe ( <math>\displaystyle Q_{F}=\{q_{F}\}  </math> ), jak i w sensie rozpoznawania
-przez pusty stos.
 }}
-W ogólności  dla ustalonego automatu ze stosem  <math>\displaystyle \mathcal{AS}  </math>
+Rodzina języków bezkontekstowych
-wprowadzone wyżej
+nie jest zamknięta na wszystkie działania boolowskie. Jak wynika z&nbsp;poniższego
-dwa sposoby rozpoznawania niekoniecznie prowadzą do tego samego języka.
+twierdzenia, jedynym działaniem boolowskim nie wyprowadzającym poza rodzinę języków
-Jednak są one równoważne, o czym przekonuje następujące twierdzenie, w dowodzie którego
+bezkontekstowych jest suma mnogościowa.
-konstruujemy odpowiednie automaty ze stosem.
 {{twierdzenie|||
-Język  <math>\displaystyle L\subset A^{*}  </math>  jest rozpoznawany przez automat ze stosem przez
-stany końcowe wtedy i tylko wtedy, gdy jest rozpoznawany przez automat ze stosem
+Rodzina języków bezkontekstowych  <math>\displaystyle \mathcal{L}_{2}  </math>  nie jest zamknięta ze względu na
-poprzez pusty stos.
+# iloczyn mnogościowy
+# uzupełnienie
 }}
 {{dowod|||
-Załóżmy, że automat  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,P,s_{0},z_{0},Q_{F})  </math>  rozpoznaje
+Dla <math>\displaystyle i=1,2 </math> niech <math>\displaystyle G_i = (\{ v_0 , v_1\},\{ a,b,c\},{v_0},P_i)</math> będą gramatykami
-przez stany końcowe język  <math>\displaystyle L=L_{F}(\mathcal{AS})  </math> . Wówczas automat
+o następujących zbiorach praw:
-<center><math>\displaystyle \mathcal{AS}'=(A,A_{S}\cup \left\{ x_{0}\right\} ,Q\cup \left\{ q_{0}',q_{e}\right\} ,P',q_{0}',x_{0}),</math></center>
+<center><math>\displaystyle \begin{array} {l}
-w którym symbol  <math>\displaystyle x_{0}  </math>  jest spoza alfabetu  <math>\displaystyle A_{S}  </math> , stany  <math>\displaystyle q_{0}',q_{e}  </math>
+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 \} \\
-nie należą do  <math>\displaystyle Q  </math> , a relacja przejść  <math>\displaystyle P'  </math>  określona jest poniżej
-<center><math>\displaystyle \begin{array} {lll}
+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 \}.
-P'= & P\: \: \cup  & \left\{ x_{0}q_{0}'\longrightarrow x_{0}z_{0}q_{0},\right. \\
-&  & zq\longrightarrow q_{e},\: \, \, q\in Q_{F},z\in A_{s}\cup \left\{ x_{0}\right\} ,\\
-&  & \left. zq_{e}\longrightarrow q_{e},\: \, z\in A_{S}\cup \left\{ x_{0}\right\} \right\}
-\end{array} </math></center>
-rozpoznaje język  <math>\displaystyle L  </math>  przez pusty stos.
+\end{array}  </math></center>
-Na odwrót, jeśli automat
+Gramatyki te są bezkontekstowe i generują, odpowiednio, następujące języki:
-ze stosem  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,P,q_{0},z_{0})  </math>  rozpoznaje poprzez pusty
-stos język  <math>\displaystyle L=L_{e}(\mathcal{AS})  </math> , to automat
-<center><math>\displaystyle \mathcal{AS}'=(A,A_{S}\cup \left\{ x_{0}\right\} ,Q\cup \left\{ q_{0}',q_{F}\right\} ,P',q_{0}',x_{0},\left\{ q_{F}\right\} ),</math></center>
+<center><math>\displaystyle L(G_{1})=\left\{ a^{n}b^{n}c^{m}:n,m\geqslant 1\right\} \in \mathcal{L}_{2}</math></center>
-w którym symbol  <math>\displaystyle x_{0}  </math>  jest spoza alfabetu  <math>\displaystyle A_{S}  </math> , stany  <math>\displaystyle q_{0}',q_{F}  </math>
+<center><math>\displaystyle L(G_{2})=\left\{ a^{n}b^{m}c^{m}:n,m\geqslant 1\right\} \in \mathcal{L}_{2}.</math></center>
-nie należą do  <math>\displaystyle Q  </math> , a relacja przejść  <math>\displaystyle P'  </math>  określona jest poniżej
-<center><math>\displaystyle P'=P\cup \left\{ x_{0}q_{0}'\longrightarrow x_{0}z_{0}q_{0},\; x_{0}q\longrightarrow q_{F},\; q\in Q\right\} </math></center>
+Języki te są bezkontekstowe, lecz ich przecięcie
-rozpoznaje język  <math>\displaystyle L  </math>  poprzez stany końcowe.
+<center><math>\displaystyle L(G_{1})\cap L(G_{2})=\left\{ a^{n}b^{n}c^{n}\, :\, n\geqslant 1\right\} \notin \mathcal{L}_{2}</math></center>
+jest językiem istotnie kontekstowym.
+Z udowodnionej właśnie własności  oraz z praw de'Morgana
+wynika, że rodzina  <math>\displaystyle \mathcal{L}_{2}  </math>  nie jest też domknięta ze względu na uzupełnienie.
 <math>\displaystyle \diamondsuit</math>   }}
-Zdefiniujemy i omówimy teraz  deterministyczne automaty ze stosem.
+==3. Jednoznaczność języków bezkontekstowych==
-W odróżnieniu
-od automatów skończenie stanowych deterministyczne automaty ze stosem posiadają
+Omówimy teraz, dość ogólnie zresztą, problem występujący w niektórych
-mniejsze możliwości rozpoznawania języków niż  automaty, które dopuszczają
+gramatykach bezkontekstowych, a polegający na
-przejścia niedeterministyczne.
+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
+nieporzą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|||
-Automat ze stosem  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,f,s_{0},z_{0},Q_{F})  </math>
+Niech <math>\displaystyle G = (V_N,V_T,v_0,P)</math> będzie gramatyką bezkontekstową.
-nazywamy
+'''Lewostronnym'''
-deterministycznym, jeśli dla każdej konfiguracji  <math>\displaystyle (z,q,a)\in A_{S}\times Q\times (A\cup \left\{ 1\right\} )  </math>
+('''prawostronnym''')
-wartość funkcji  <math>\displaystyle f(z,q,a)  </math>  jest zbiorem co najwyżej jednoelementowym, czyli
+'''wyprowadzeniem''' słowa <math>\displaystyle w \in {V_T}^*</math> w gramatyce <math>\displaystyle G</math> nazywamy
-<math>\displaystyle \sharp f(z,q,a)\leq 1  </math> oraz jeśli  <math>\displaystyle f(z,q,1)\neq \emptyset   </math> , to  <math>\displaystyle f(z,q,a)=\emptyset   </math>
+wyprowadzenie <center><math>\displaystyle v_0 \mapsto w_1 \mapsto \ldots.. \mapsto w_n = w</math></center>
-dla każdego  <math>\displaystyle a\in A  </math> .
+takie,
+że dla każdego <math>\displaystyle  i=0,\ldots,n-1, \;\; w_{i+1} </math> jest
+generowane bezpośrednio z <math>\displaystyle w_i</math> przez zastąpienie pierwszego z lewej (prawej)
+symbolu nieterminalnego występującego w&nbsp;słowie <math>\displaystyle w_i</math>.
 }}
-A więc deterministyczny automat ze stosem  ma możliwość co najwyżej
+Jeśli chcemy zaznaczyć, że wyprowadzenie jest lewostronne lub
-jednego przejścia z dowolnej konfiguracji
+prawostronne, to posługujemy się zapisem
-<math>\displaystyle (z,q,a)\in A_{S}\times Q\times (A\cup \left\{ 1\right\} )  </math>
-oraz jeśli istnieje przejście dla określonego stanu i symbolu ze stosu pod wpływem
-słowa pustego, to jest ono jedynym możliwym dla tego układu w tym automacie.
-Język rozpoznawany przez deterministyczny automat ze stosem nazywamy językiem
+<center><math>\displaystyle v_{0}\mapsto_{L}^{*}w,\; v_{0}\mapsto_{P}^{*}w</math></center>
-deterministycznym.
-O tym, że w przeciwieństwie do klasy języków regularnych,
+Każde wyprowadzenie słowa w gramatyce bezkontekstowej
-języki rozpoznawane przez deterministyczne automaty ze stosem stanowią właściwą
+można tak uporządkować, by sekwencja produkcji
-podklasę wszystkich języków akceptowanych przez automaty ze stosem, przekonuje
+tworzyła prawostronne lub
-przykład.
+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&nbsp;teorii, jak i zastosowaniach gramatyki bezkontekstowe jednoznaczne,
+których definicję podajemy poniżej.
-{{przyklad|||
+{{definicja|||
-Język  <math>\displaystyle L=\{a^{n}b^{n}:\: n\geq 1\}\cup \{a^{n}b^{2n}:\: n\geq 1\}  </math>
+Gramatyka bezkontekstowa <math>\displaystyle G</math> jest '''jednoznaczna''',
-rozpoznawany przez automat ze stosem opisany grafem <br>
+wtedy i&nbsp;tylko wtedy,
+gdy każde słowo generowane przez tę gramatykę ma dokładnie jedno wyprowadzenie
+lewostronne (prawostronne).
+Język bezkontekstowy <math>\displaystyle L</math> nazywamy jednoznacznym, jeśli istnieje
+jednoznaczna gramatyka bezkontekstowa generująca
+ten język.
-rys 4. ja-lekcja11-w-rys14 <br>
+}}
-nie jest językiem deterministycznym. Zauważmy bowiem,
+Jednoznaczność gramatyki oznacza istnienie
-że deterministyczny automat ze stosem, aby zaakceptować słowo  <math>\displaystyle a^{n}b^{n}  </math> ,
+dokładnie jednego drzewa wywodu dla każdego generowanego słowa.
-dla kontrolowania ilości liter  <math>\displaystyle a  </math>  i  <math>\displaystyle b  </math>  wykorzystuje stos, wprowadzając
+W klasie gramatyk bezkontekstowych problem jednoznaczności jest nierozstrzygalny.
-przy czytaniu każdej litery  <math>\displaystyle a  </math>  ustalony symbol na stos, na przykład  <math>\displaystyle "a"  </math>
+W rozdziale poświęconym algorytmicznej rozstrzygalności wrócimy do
-i usuwając sekwencyjnie te symbole przy czytaniu liter  <math>\displaystyle b  </math> .
+tego zagadnienia. Oczywiście   wobec powyższego nierozstrzygalny jest też problem
-Dla zaakceptowania słowa  <math>\displaystyle a^{n}b^{2n}  </math>  podobne postępowanie prowadzi do
+jednoznaczności języka.
-wpisywania na stos słowa  <math>\displaystyle "aa"  </math>  z alfabetu stosu dla każdej litery  <math>\displaystyle a  </math>
+Problem jednoznaczności gramatyki i języka jest rozstrzygalny w podklasach języków
-i usuwaniu pojedynczego symbolu przy czytaniu  <math>\displaystyle b  </math> . Jest to jedyny sposób kontroli
+bezkontekstowych, na przykład dla klasy języków ograniczonych, to znaczy takich
-ilości liter, a opisane działanie automatu
+<math>\displaystyle L\subset A^{*}  </math> , że  <math>\displaystyle L\subset w_{1}^{*}...w_{n}^{*}  </math>  dla pewnych
-jest źródłem jego istotnej niedeterministyczności. Bez trudu można zauważyć,  że
+słów  <math>\displaystyle w_{1},...,w_{n}\in A^{*}  </math> .
-każdy automat ze stosem rozpoznający język  <math>\displaystyle L  </math>  będzie zawierać ten niedeterministyczny
-układ w&nbsp;swojej strukturze.
-Aby lepiej uchwycić istotę tego niedeterminizmu zauważmy, że automat ze stosem określony
+{{przyklad|||
-grafem
+Język  <math>\displaystyle \left\{ a^{n}b^{n+m}c^m\, :\, n,m>0\right\}   </math>
-{}
+generowany przez gramatykę  <math>\displaystyle G=(V_{N},V_{T},v_{0},P)  </math> , gdzie  <math>\displaystyle V_{N}=\{v_{0},v_{1}\}  </math> ,
+<math>\displaystyle V_{T}=\{a,b,c\}  </math>  oraz<br>
+<math>\displaystyle P= v_{0}\rightarrow v_1 v_2 , \;\; v_1 \rightarrow av_{1}b\;|ab, \;\; v_2 \rightarrow  bv_2c,  \;|bc   </math> <br>
+jest, jak łatwo sprawdzić, językiem jednoznacznym.<br>
-Rys 5   ja-lekcja11-w-rys5 <br>
+}}
-rozpoznaje język  <math>\displaystyle L=\{a^{n}b^{n}:\: n\geq 1\}  </math>  i jest deterministyczny.
+Mówimy, że język  <math>\displaystyle L\in \mathcal{L}_{2}  </math>  jest '''niejednoznaczny''',
+jeśli nie jest jednoznaczny, czyli nie istnieje gramatyka jednoznaczna
+generująca ten język. Przykładem języka niejednoznacznego
+jest
-}}
+<center><math>\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\}. </math></center>
-Każdy język rozpoznawany przez deterministyczny automat ze stosem
+Uzasadnienie tego faktu jest dosyć żmudne i dlatego zostało tutaj pominięte.
-jest oczywiście (dlaczego?) jednoznaczny. Jednoznaczność języka nie implikuje jednak
-jego deterministyczności
-o czym  przekonuje zamieszczony poniżej przykład.
-{{przyklad|||
+Zauważmy na koniec tego krótkiego omówienia problematyki jednoznaczności gramatyk,
-Język  <math>\displaystyle L=\{a^{n}b^{n}:\: n\geq 1\}\cup \{a^{n}b^{2n}:\: n\geq 1\}  </math> ,
+że każdy język regularny (ale nie każda gramatyka regularna) jest
-który jest rozpoznawany przez automat ze stosem z poprzedniego przykładu, nie
+jednoznaczny. Jednoznaczna
-jest, jak wiemy, deterministyczny, ale jest jednoznaczny.
+jest bowiem gramatyka otrzymana z automatu deterministycznego generującego ten
+język.
-}}
+Jednoznaczny jest również język bezkontekstowy, który jest iloczynem
+<math>\displaystyle L\cap R  </math> , gdzie  <math>\displaystyle L\in \mathcal{L}_{2}  </math>  i jest językiem jednoznacznym,
+a  <math>\displaystyle R\in \mathcal{L}_{3}  </math> . Gramatyka tego języka, skonstruowana
+w punkcie [[##p1|Uzupelnic p1|]] w twierdzeniu [[##tw 2|Uzupelnic tw 2|]] jest jednoznaczna, co wynika stąd, że automat
+rozpoznający  <math>\displaystyle R  </math>  jest deterministyczny.
-==Gramatyki bezkontekstowe i automaty ze stosem==
+==4. Problemy rozstrzygalne algorytmicznie==
-Automaty ze stosem charakteryzują rodzinę języków bezkontekstowych w tym samym
+Podobnie jak dla języków regularnych tak i w przypadku bezkontekstowych lemat
-sensie, w jakim automaty skończenie stanowe charakteryzują języki regularne.
+o pompowaniu wykorzystuje się do uzasadnienie rozstrzygalności pewnych
+problemów.
+Dla rodziny języków bezkontekstowych mamy następujące twierdzenie.
 {{twierdzenie|||
+W rodzinie j{e}zyków bezkontekstowych  <math>\displaystyle \mathcal{L}_{2}  </math>  nast{e}puj{a}ce
-Rodzina języków rozpoznawanych przez automaty ze stosem jest równa rodzinie
+problemy s{a} rozstrzygalne:
-języków bezkontekstowych  <math>\displaystyle \mathcal{L}_{2}  </math> .
+# problem niepustości języka,  <math>\displaystyle L\neq \emptyset   </math>
+# problem nieskończoności języka,  <math>\displaystyle card\, L=\aleph _{0}  </math>
+# problem należenia słowa <math>\displaystyle w</math> do języka <math>\displaystyle L</math>
 }}
 {{dowod|||
-(szkic)
+Aby udowodnić  punkt 1 wykorzystamy następującą równoważność:
-Dla dowodu, że każdy język bezkontekstowy jest rozpoznawany przez odpowiedni
-automat ze stosem, rozważmy gramatykę  <math>\displaystyle G=(V_{N},V_{T},v_{0},P_{G})  </math>
-bezkontekstową
-w postaci normalnej Greibach i załóżmy, że słowo puste  <math>\displaystyle 1  </math>  nie należy do
-języka  <math>\displaystyle L(G)  </math>  generowanego przez tę gramatykę. Podamy konstrukcję
-automatu ze stosem  <math>\displaystyle AS  </math> , który, jak można wykazać, akceptuje poprzez pusty stos
-język  <math>\displaystyle L(G)  </math> . Niech
-<center><math>\displaystyle \mathcal{AS}=(V_{T},V_{N}\cup V_{T},\left\{ q\right\} ,f,q,v_{0})</math></center>
+<center><math>\displaystyle L\neq \emptyset \; \Longleftrightarrow \; \exists w\in L\, :\, |w|\leqslant N, </math></center>
-gdzie funkcja  <math>\displaystyle f:(V_{N}\cup V_{T})\times \{q\}\times (V_{T}\cup \left\{ 1\right\} )\longrightarrow \mathcal{P}_{sk}((V_{N}\cup V_{T})^{*}\times \{q\})  </math>
+Uzasadnienie tej równoważności polega
-określona jest następujaco. Dla dowolnych  <math>\displaystyle v\in V_{N},\: a\in V_{T}  </math>
-<center><math>\displaystyle f(v,q,1)=\{(\overleftarrow{x}a,q)\: :\: v\rightarrow ax\in P_{G}\}</math></center>
+na rozk{}adzie s{}owa  <math>\displaystyle w  </math>  spe{}niaj{a}cego warunek  <math>\displaystyle N<|w|  </math>
+(zgodnie z oznaczeniami i tezą lematu o pompowaniu) i zastąpieniu go s{}owem
+<math>\displaystyle u_{1}uu_{2}  </math> , które jest istotnie krótsze. Po sko{n}czonej ilo{s}ci takich
+skracających kroków  dostaniemy s{}owo nale{z}{a}ce do j{e}zyka
+<math>\displaystyle L  </math>  i spe{}niaj{a}ce
+warunek  <math>\displaystyle |w|\leqslant N  </math> .
-<center><math>\displaystyle f(a,q,a)=\{(1,q)\}</math></center>
+W uzasadnieniu punktu 2 wykorzystamy równoważność
-oraz ma wartość równą zbiorowi pustemu  <math>\displaystyle \emptyset   </math>  we wszystkich pozostałych
+<center><math>\displaystyle card\, L=\aleph _{0}\Longleftrightarrow \; \exists w\in L\, :\, N<|w|\leqslant N+M, </math></center>
-przypadkach.
-Jest to więc automat o jednym stanie  <math>\displaystyle q  </math> , alfabetem wejściowym jest
+gdzie  <math>\displaystyle M,N  </math>  są stałymi z lematu o pompowaniu.
-alfabet terminalny  <math>\displaystyle V_{T}  </math> , alfabetem stosu jest suma mnogościowa alfabetu
-symboli nieterminalnych  <math>\displaystyle V_{N}  </math>  i terminalnych  <math>\displaystyle V_{T}  </math> ,
-a symbol początkowy
-stosu jest symbolem startowym gramatyki. Istotą działania automatu  <math>\displaystyle AS  </math>  jest
-symulacja
-lewostronnego wyprowadzenia w gramatyce  <math>\displaystyle G.  </math>
-Pełne uzasadnienie podanej konstrukcji znajduje sie na końcu tego wykładu,
-w części "dla dociekliwych".
-Załóżmy teraz, że automat  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,f,q_{0},z_{0})  </math>  akceptuje poprzez
+Przyjmując, iż j{e}zyk  <math>\displaystyle L  </math>  jest niesko{n}czony, wnioskujemy, {z}e
-pusty stos język  <math>\displaystyle L(\mathcal{AS})  </math> . Konstrukcja gramatyki bezkontekstowej
+istnieją w tym języku słowa dowolnie d{}ugie.
-<math>\displaystyle G  </math> , która generuje ten sam język przebiega następująco.
+Niech  <math>\displaystyle w\in L  </math>  i  <math>\displaystyle |w|>N  </math> . Je{s}li  <math>\displaystyle w  </math>  nie spe{}nia warunku
-Niech  <math>\displaystyle G=((Q\times A_{S}\times Q)\cup \left\{ v_{0}\right\} ,A,v_{0},P_{G})  </math> ,
+<math>\displaystyle |w|\leqslant N+M  </math> , to stosujemy lemat o pompowaniu dla  <math>\displaystyle i=0  </math> , uzyskując
-gdzie  <math>\displaystyle v_{0}\notin Q\cup A_{S}\cup A  </math> . Wprowadzamy do zbioru praw  <math>\displaystyle P_{G}  </math>
+s{}owo  <math>\displaystyle u_{1}uu_{2}  </math>  nale{z}{a}ce do j{e}zyka i istotnie krótsze
-wyłącznie następujące prawa:
+od  <math>\displaystyle w  </math> . Z warunku  <math>\displaystyle |w_{1}w_{2}|\leqslant |w_{1}uw_{2}|\leqslant M  </math>
-#  <math>\displaystyle v_{0}\rightarrow (q_{0},z_{0},q)  </math>  dla wszystkich stanów  <math>\displaystyle q\in Q  </math> ,
+(punkt 1 tezy lematu o pompowaniu) wynika, i{z} ró{z}nica d{}ugo{s}ci
-#  <math>\displaystyle (q,z,q_{1})\rightarrow a(q_{k+1},z_{k},q_{k})(q_{k},z_{k-1},q_{k-1})\ldots (q_{2},z_{1},q_{1})  </math>
+tych s{}ów nie mo{z}e by{c} wi{e}ksza ni{z} sta{}a  <math>\displaystyle M  </math> .
-dla dowolnych stanów  <math>\displaystyle q,q_{1},\ldots ,q_{k+1}\in Q,  \displaystyle \, a\in A\cup \left\{ 1\right\} ,\, z,z_{1},\ldots z_{k}\in A_{S}  </math>
+Zatem po sko{n}czonej ilo{s}ci kroków uzyskujemy s{}owo nale{z}{a}ce
-jeśli  <math>\displaystyle (z_{1}...z_{k},q_{k+1})\in f(z,q,a)  </math> ,
+do j{e}zyka i spe{}niaj{a}ce {z}{a}dany warunek.
-#  <math>\displaystyle (q,z,q_{1})\rightarrow a\in P_{G}  </math>  jeśli  <math>\displaystyle (1,q_{1})\in f(z,q,a)  </math> .
-{ Mamy więc następującą równoważność:
+Implikacja w przeciwną stronę ( <math>\displaystyle \Leftarrow   </math> ) wynika bezpo{s}rednio
+z lematu o pompowaniu. Istnieje mianowicie niesko{n}czony zbiór słów w postaci
-<center><math>\displaystyle
+<center><math>\displaystyle u_{1}w_{1}^{i}uw_{2}^{i}u_{2}\in L</math></center>
-\begin{array} {c}
-\begin{array} {c}
-(q,z,q_{1})\rightarrow a(q_{k+1},z_{k},q_{k})(q_{k},z_{k-1},q_{k-1})\ldots (q_{2},z_{1},q_{1})\in P_{G}
-\end{array} \\
-\begin{array} {c}
-\, \Leftrightarrow \, (z_{1}\ldots z_{k},q_{k+1})\in f(z,q,a),
-\end{array}
-\end{array}
-</math></center>
-}
+dla  <math>\displaystyle i=0,1,2,....  </math>
-która w szczególności dla  <math>\displaystyle k=0  </math>  przyjmuje postać
+Punkt 3 twierdzenia wymaga podania odpowiedniego algorytmu. Jego prezentacją i omówieniem
+zajmujemy się poniżej.
-<center><math>\displaystyle (q,z,q_{1})\rightarrow a\in P_{G}\, \Leftrightarrow \, (1,q_{1})\in f(z,q,a)</math></center>
-i oznacza dla gramatyki wymazywanie symboli nieterminalnych, a dla automatu
-wymazywanie symboli stosu.
-Skonstruowana gramatyka  <math>\displaystyle G  </math>  odtwarza działanie automatu  <math>\displaystyle AS  </math>  działającego
-pod wpływem słowa wejściowego  <math>\displaystyle w  </math> . Pełne uzasadnienie podanej konstrukcji znajduje się
-na końcu tego wykładu,
-w części "dla dociekliwych".
 <math>\displaystyle \diamondsuit</math>   }}
-Z konstrukcji przedstawionej w szkicu dowodu twierdzenia wynika, że każdy język bezkontekstowy
+{Algorytm CYK - przynależność słowa do języka.}
-może być rozpoznawany poprzez pusty stos przez automat ze stosem o jednym stanie. Określenie
-algorytmów na podstawie powyższego twierdzenia proponujemy  jako ćwiczenie.
-Powróćmy na moment do języka Łukasiewicza. Język ten oraz jego  gramatyka
+Rozważmy problem przynależności słowa <math>\displaystyle w</math> do danego języka, generowanego
-zostały wprowadzone podczas pierwszego wykładu poswięconego  językom
+przez gramatykę bezkontekstową <math>\displaystyle G</math>. Jest to problem rozstrzygalny.
-bezkontekstowym. Każde słowo, generowane
+Bardzo łatwo podać algorytm, wykorzystujący postać normalną
-przez tę gramatykę, jest pewnym wyrażeniem algebraicznym zapisanym w notacji
+Greibach. Po sprowadzeniu gramatyki <math>\displaystyle G</math> do postaci normalnej Greibach prawa strona
-polskiej, prefiksowej, bez użycia nawiasów.
+każdej produkcji rozpoczyna się symbolem terminalnym i jest to
-Bez trudności można określić gramatykę bezkontekstową, która generuje język Łukasiewicza,
+jedyny symbol terminalny.
-w którym słowa zapisywane są w wersji postfiksowej. Wystarczy bowiem przyjąć:
+Zatem, jeśli <math>\displaystyle w=a_1a_2...a_n</math>, to należy zbadać
-<math>\displaystyle G = (V_N,V_T,v_0,P)</math>, gdzie <math>\displaystyle V_N=\{v_0 \}</math>,  <math>\displaystyle V_{T}=\left\{ a,b,+,*\right\}   </math> ,
+wszystkie wywody w <math>\displaystyle G</math>, z symbolu początkowego <math>\displaystyle S</math>, o długości dokładnie <math>\displaystyle |w|</math>,
-<math>\displaystyle v_{0}=v  </math>  oraz <math>\displaystyle P= \{v \rightarrow a, v \rightarrow b, v \rightarrow vv+, v \rightarrow vv* \}</math>.
+to znaczy wywody złożone z
-Język
+dokładnie <math>\displaystyle |w|</math> kroków. Jeśli dla każdego symbolu nieterminalnego istnieje co
-{}ukasiewicza jest więc teraz zbiorem
+najwyżej <math>\displaystyle k</math> produkcji w gramatyce <math>\displaystyle G</math>, w których pojawia się on po lewej stronie,
+to algorytm będzie działał w czasie <math>\displaystyle O(k^{|w|})</math>. Metoda ta jest
+jednak bardzo nieefektywna. Czasochłonne jest też samo sprowadzenie gramatyki  <math>\displaystyle G</math>
+do postaci normalnej Greibach.
-<center><math>\displaystyle L(G)=\left\{ a,\: b,ab+,bab+*,ab+ab+*,\ldots \right\}. </math></center>
+Istnieje  szybszy algorytm rozwiązujący problem
+przynależności do języka. Jest to algorytm
+Cocke'a-Youngera-Kasamiego, w skrócie CYK.
-Oczywiście język ten jest  rozpoznawany przez odpowiedni automat ze stosem.
+Algorytm CYK działa w oparciu o ideę programowania dynamicznego
-Określeniem takiego automatu zajmiemy się podczas ćwiczeń. Warto zauważyć,
+. Rozważmy słowo <math>\displaystyle w=a_1a_2...a_n</math> oraz gramatykę <math>\displaystyle G</math>.
-że rozpoznając słowa języka Łukasiewicza w postfiksowej postaci,
+Niech zbiór <math>\displaystyle V_i^j</math> zawiera wyłącznie te symbole nieterminalne, z których można wywieść
-automat ze stosem działa dokładnie tak, jak obliczane są
+słowo <math>\displaystyle a_ia_{i+1}...a_{i+j-1}</math>, czyli
-wartości wyrażeń arytmetycznych we współczesnych procesorach.
+<center><math>\displaystyle V_i^j=\{v \in V_N: v \Rightarrow^*_G a_i a_{i+1}... a_{i+j-1} \}.</math></center>
-Automat ze stosem, czytając wyrażenie od lewej do prawej, zapisuje
-wyniki częściowe na stosie, a operacje wykonywane są
-zawsze na ostatnich elementach stosu.
-Dla bardziej dociekliwych studentów proponujemy poniżej pełny dowód twierdzenia
+Mamy zatem następującą równoważność: <center><math>\displaystyle w \in L(G) \Leftrightarrow
-orzekajacego, że języki rozpoznawane przez automaty ze stosem to dokładnie języki
+v_0 \in V_1^n.</math></center>
-bezkontekstowe.
----- dla dociekliwych - start ----
+{{algorytm|||
-{{twierdzenie|||
+{''Cocke-Younger-Kasami'' - sprawdza, czy dane słowo
-Rodzina języków rozpoznawanych przez automaty ze stosem jest równa rodzinie
+należy do języka generowanego przez gramatykę bezkontekstową}
-języków bezkontekstowych  <math>\displaystyle \mathcal{L}_{2}  </math> .
-}}
+[1]
-{{dowod|||
+Wejście: <math>\displaystyle G=(V_N, V_T, P, v_0)</math>, <math>\displaystyle w \in V_T^*</math> - gramatyka
-Dla dowodu, że każdy język bezkontekstowy jest rozpoznawany przez odpowiedni
+bezkontekstowa i słowo <math>\displaystyle w=a_1a_2...a_n</math> o długości <math>\displaystyle n</math>
-automat ze stosem, rozważmy gramatykę  <math>\displaystyle G=(V_{N},V_{T},v_{0},P_{G})  </math>  bezkontekstową,
-w postaci normalnej Greibach i załóżmy, że słowo puste  <math>\displaystyle 1  </math>  nie należy do
-języka  <math>\displaystyle L(G)  </math>  generowanego przez tę gramatykę. Konstruujemy teraz
-automat ze stosem  <math>\displaystyle AS  </math> , który, jak udowodnimy, akceptuje poprzez pusty stos
-język  <math>\displaystyle L(G)  </math> . Niech
-<center><math>\displaystyle \mathcal{AS}=(V_{T},V_{N}\cup V_{T},\left\{ q\right\} ,f,q,v_{0})</math></center>
+Wyjście: TAK lub NIE - odpowiedź na pytanie, czy <math>\displaystyle w \in
+L(G)</math>.
-gdzie funkcja  <math>\displaystyle f:(V_{N}\cup V_{T})\times \{q\}\times (V_{T}\cup \left\{ 1\right\} )\longrightarrow \mathcal{P}_{sk}((V_{N}\cup V_{T})^{*}\times \{q\})  </math>
+<math>\displaystyle G \leftarrow </math>''PostaćNormalnaChomsky'ego''<math>\displaystyle (G)</math>;
-określona jest następujaco. Dla dowolnych  <math>\displaystyle v\in V_{N},\: a\in V_{T}  </math>
-<center><math>\displaystyle f(v,q,1)=\{(\overleftarrow{x}a,q)\: :\: v\rightarrow ax\in P_{G}\}</math></center>
+'''for''' <math>\displaystyle i=1,...,n\displaystyle V_i^1 \leftarrow \{v \in V_N:\ (v \rightarrow a) \in P, a
+\in V_T\ \wedge\ a_i=a \}</math>;
-<center><math>\displaystyle f(a,q,a)=\{(1,q)\}</math></center>
+'''endfor'''
-oraz równa jest zbiorowi pustemu  <math>\displaystyle \emptyset   </math>  we wszystkich pozostałych
+'''for''' <math>\displaystyle j=2,...,n</math>
-przypadkach.
-A zatem jest to automat o jednym stanie  <math>\displaystyle q  </math> , alfabetem wejściowym jest
+'''for''' <math>\displaystyle i=1,...,n-j+1\displaystyle V_i^j \leftarrow </math>;
-alfabet terminalny  <math>\displaystyle V_{T}  </math> , alfabetem stosu jest suma mnogościowa alfabetu
-symboli nieterminalnych  <math>\displaystyle V_{N}  </math>  i terminalnych  <math>\displaystyle V_{T}  </math> , a symbol początkowy
-stosu jest symbolem startowym gramatyki. Działanie automatu  <math>\displaystyle AS  </math>  symuluje
-lewostronne wyprowadzenie w gramatyce  <math>\displaystyle G.  </math>
-Dla dowolnego słowa  <math>\displaystyle w\in L(G)  </math>  istnieje lewostronne wyprowadzenie
+'''for''' <math>\displaystyle k=1,...,j-1\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}\}</math>;
-<center><math>\displaystyle v_{0}\mapsto a_{1}v_{1}y_{1}\mapsto a_{1}a_{2}v_{2}y_{2}\mapsto ...\mapsto a_{1}...a_{k-1}v_{k-1}\mapsto a_{1}...a_{k}=w, </math></center>
+'''endfor'''
-gdzie  <math>\displaystyle a_{i}\in V_{T}  </math> ,  <math>\displaystyle v_{i}\in V_{N}  </math>  oraz  <math>\displaystyle y_{i}\in V_{N}^{*}  </math> ,
+'''endfor'''
-gdyż gramatyka jest w postaci Greibach. Odpowiada temu wyprowadzeniu następujace
-działanie automatu  <math>\displaystyle \mathcal{AS}  </math> :
-<center><math>\displaystyle (v_{0},q)\mid \! \Longrightarrow ^{1}(\overleftarrow{y_{1}}v_{1}a_{1},q)\mid \! \Longrightarrow ^{a_{1}}(\overleftarrow{y_{1}}v_{1},q)\mid \! \Longrightarrow ^{1}(\overleftarrow{y_{2}}v_{2}a_{2},q)\mid \! \Longrightarrow ^{a_{2}}...</math></center>
+'''endfor'''
-<center><math>\displaystyle ...\mid \! \Longrightarrow ^{1}(v_{k-1}a_{k-1},q)\mid \! \Longrightarrow ^{a_{k-1}}(v_{k-1},q)\mid \! \Longrightarrow ^{1}(a_{k},q)\mid \! \Longrightarrow ^{a_{k}}(1,q).</math></center>
+'''if''' <math>\displaystyle v_0 \in V_1^n</math>
-A to oznacza zaakceptowanie słowa  <math>\displaystyle w  </math>  poprzez pusty stos. Zatem  <math>\displaystyle L(G)\subset L(\mathcal{AS})  </math> .
+'''return''' '''TAK''', <math>\displaystyle w \in L(G)</math>;
-Dla dowodu inkluzji w przeciwną stronę wykorzystamy implikację
-<center><math>\displaystyle (v_{0},q)\mid \! \Longrightarrow ^{w}(\overleftarrow{x},q)\; w\; \mathcal{AS}\Longrightarrow v_{0}\mapsto_{L}^{*}wx\; w\; G, </math></center>
+'''else'''
-która ma miejsce dla dowolnego  <math>\displaystyle w\in V_{T}^{*}  </math> . Implikację tę udowodnimy
+'''return''' '''NIE''', <math>\displaystyle w \not \in L(G)</math>;
-indukcyjnie ze względu na długość słowa  <math>\displaystyle w  </math> . Dla słowa pustego  <math>\displaystyle 1  </math>
-oraz dla  <math>\displaystyle w=a\in V_{T}  </math>  powyższa implikacja wynika bezpośrednio z definicji
-automatu ze stosem. Załóżmy teraz, że  <math>\displaystyle (v_{0},q)\mid \! \Longrightarrow ^{w}(\overleftarrow{x},q)  </math>
-w  <math>\displaystyle \mathcal{AS}  </math>  i niech  <math>\displaystyle w=w_{1}a  </math>  dla  <math>\displaystyle a\in V_{T}  </math>  i  <math>\displaystyle w_{1}\in V_{T}^{*}  </math> .
-Mamy więc  <math>\displaystyle (v_{0},q)\mid \! \Longrightarrow ^{w_{1}}(\overleftarrow{y},q)  </math>
-i  <math>\displaystyle (\overleftarrow{y},q)\mid \! \Longrightarrow ^{a}(\overleftarrow{x},q)  </math>
-w automacie  <math>\displaystyle \mathcal{AS}  </math> . Z założenia indukcyjnego wnioskujemy, że  <math>\displaystyle v_{0}\mapsto_{L}^{*}w_{1}y  </math>
-w  <math>\displaystyle G  </math> . W przypadku, gdy   <math>\displaystyle y=a  </math> , wnioskujemy z określenia automatu ze
-stosem, że  <math>\displaystyle x=1  </math>  i wtedy  <math>\displaystyle v_{0}\mapsto_{L}^{*}w_{1}a=w  </math>  w  <math>\displaystyle G  </math> .
-Jeśli natomiast  <math>\displaystyle y=vy'  </math> dla  <math>\displaystyle v\in V_{N}  </math>  i  <math>\displaystyle y'\in V_{N}^{*}  </math> ,
-to w automacie  <math>\displaystyle \mathcal{AS}  </math>  ma miejsce wyprowadzenie
-<center><math>\displaystyle (v_{0},q)\mid \! \Longrightarrow ^{w_{1}}(\overleftarrow{y},q)=(\overleftarrow{y'}v,q)\mid \! \Longrightarrow ^{1}(\overleftarrow{y'}\overleftarrow{x',}q)\mid \! \Longrightarrow ^{a}(\overleftarrow{x},q), </math></center>
+'''endif'''
-gdzie  <math>\displaystyle x'=az,\;   \displaystyle a\in V_{T}  </math>  i  <math>\displaystyle z\in V_{N}^{*}  </math>  i prawo  <math>\displaystyle v\rightarrow x'\in P_{G}  </math> .
+}}
-W dalszym ciągu działania automatu następuje krok  <math>\displaystyle (\overleftarrow{y'}\overleftarrow{x',}q)\mid \! \Longrightarrow ^{a}(\overleftarrow{x},q)  </math> ,
-a to w konsekwencji oznacza, że w&nbsp;gramatyce  <math>\displaystyle G  </math>  ma miejsce wyprowadzenie
-<center><math>\displaystyle v_{0}\mapsto_{L}^{*}w_{1}y=w_{1}vy'\mapsto_{L}^{*}w_{1}x'y''\mapsto_{L}^{*}w_{1}azy'=wx. </math></center>
+Algorytm CYK działa w czasie <math>\displaystyle |w|^3</math>, gdzie <math>\displaystyle |w|</math> jest długością
+słowa, o którego przynależność do języka pytamy.
-Załóżmy teraz, że automat  <math>\displaystyle \mathcal{AS}=(A,A_{S},Q,f,q_{0},z_{0})  </math>  rozpoznaje
+{{przyklad|||
-z pustym stosem język  <math>\displaystyle L(\mathcal{AS})  </math> . Skonstruujemy gramatykę bezkontekstową
+Zbadamy, czy słowo <math>\displaystyle w=bbaaaa</math> należy do języka generowanego
-<math>\displaystyle G  </math> , generującą ten sam język. Niech  <math>\displaystyle G=((Q\times A_{S}\times Q)\cup \left\{ v_{0}\right\} ,A,v_{0},P_{G})  </math> ,
+gramatyką:
-gdzie  <math>\displaystyle v_{0}\notin Q\cup A_{S}\cup A  </math> . Do zbioru praw  <math>\displaystyle P_{G}  </math>  zaliczymy
-wyłącznie następujące prawa:
-#  <math>\displaystyle v_{0}\rightarrow (q_{0},z_{0},q)  </math>  dla wszystkich stanów  <math>\displaystyle q\in Q  </math> ,
-#  <math>\displaystyle (q,z,q_{1})\rightarrow a(q_{k+1},z_{k},q_{k})(q_{k},z_{k-1},q_{k-1})\ldots (q_{2},z_{1},q_{1})  </math>
-dla dowolnych stanów  <math>\displaystyle q,q_{1},\ldots ,q_{k+1}\in Q,  \displaystyle \, a\in A\cup \left\{ 1\right\} ,\, z,z_{1},\ldots z_{k}\in A_{S}  </math>
-jeśli  <math>\displaystyle (z_{1}...z_{k},q_{k+1})\in f(z,q,a)  </math> ,
-#  <math>\displaystyle (q,z,q_{1})\rightarrow a\in P_{G}  </math>  jeśli  <math>\displaystyle (1,q_{1})\in f(z,q,a)  </math> .
-{ Mamy więc następującą równoważność:
+<center><math>\displaystyle \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
+\endaligned</math></center>
-<center><math>\displaystyle
+gdzie <math>\displaystyle v</math> jest symbolem początkowym.
-\begin{array} {c}
+}}
-\begin{array} {c}
-(q,z,q_{1})\rightarrow a(q_{k+1},z_{k},q_{k})(q_{k},z_{k-1},q_{k-1})\ldots (q_{2},z_{1},q_{1})\in P_{G}
-\end{array} \\
-\begin{array} {c}
-\, \Leftrightarrow \, (z_{1}\ldots z_{k},q_{k+1})\in f(z,q,a),
-\end{array}
-\end{array}
-</math></center>
-}
+Poniższa animacja ilustruje działanie algorytmu CYK.
-która w szczególności dla  <math>\displaystyle k=0  </math>  przyjmuje postać
-<center><math>\displaystyle (q,z,q_{1})\rightarrow a\in P_{G}\, \Leftrightarrow \, (1,q_{1})\in f(z,q,a)</math></center>
-i oznacza dla gramatyki wymazywanie symboli nieterminalnych, a dla automatu
-wymazywanie symboli stosu.
-Skonstruowana gramatyka  <math>\displaystyle G  </math>  odtwarza działanie automatu  <math>\displaystyle AS  </math>  działającego
-pod wpływem słowa wejściowego  <math>\displaystyle w,  </math>  co udowodnimy poniżej. W tym celu wykażemy
-indukcyjnie ze względu na długość słowa  <math>\displaystyle w\in A^{*}  </math>  następującą równoważność:
-<center><math>\displaystyle \begin{array} {c}
-(q,z,q_{1})\mapsto^{*}_{G}w(q_{k+1},z_{k},q_{k})\ldots (q_{2},z_{1},q_{1})\, \Leftrightarrow \, \\
-\, \Leftrightarrow \, (z,q)\, \mid \! \Longrightarrow ^{w}\, (z_{1}\ldots z_{k},q_{k+1})
-\end{array} </math></center>
-Dla  <math>\displaystyle w=a\in A  </math>  równoważność redukuje się do obserwacji [[##row1|Uzupelnic row1|]]. Załóżmy
-teraz, że słowo  <math>\displaystyle w=w_{1}a  </math>  oraz że w gramatyce  <math>\displaystyle G  </math>  mamy wyprowadzenie
-<math>\displaystyle (q,z,q_{1})\Rightarrow _{G}^{*}w_{1}a(q_{k+1},z_{k},q_{k})\ldots (q_{2},z_{1},q_{1})  </math> .
-Z postaci gramatyki  <math>\displaystyle G  </math>  wynika, że to wyprowadzenie można przedstawić nastepująco:
-<center><math>\displaystyle \begin{array} {c}
-(q,z,q_{1})\mapsto_{G}^{*}w_{1}(q',z',q_{p})(q_{p},z_{p-1},q_{p-1})\ldots (q_{2},z_{1},q_{1})\\
-\mapsto_{G}w_{1}a(q_{k+1},z_{k},q_{k})\ldots (q_{p+1},z_{p},q_{p})(q_{p},z_{p-1},q_{p-1})\ldots (q_{2},z_{1},q_{1})
-\end{array} </math></center>
-dla pewnego  <math>\displaystyle p\leq k  </math>  i odpowiednich  <math>\displaystyle q,q',q_{1},\ldots ,q_{k+1}\in Q,\, z,z',z_{1},\ldots z_{k}\in A_{S}  </math> .
-Z założenia indukcyjnego wynika, iż pierwszy fragment wyprowadzenia jest w&nbsp;automacie
-<math>\displaystyle AS  </math>  zastąpiony równoważnie poprawnym obliczeniem
-<center><math>\displaystyle (z,q)\, \mid \! \Longrightarrow ^{w_{1}}\, (z_{1}\ldots z_{p-1}z',q'),</math></center>
-a drugi
-<center><math>\displaystyle (z_{1}\ldots z_{p-1}z',q')\, |\! \! \! \Longrightarrow ^{a}\, (z_{1}\ldots z_{p-1}z_{p}...z_{k},q_{k+1}).</math></center>
-A to oznacza, że w automacie  <math>\displaystyle AS  </math>  mamy poprawne obliczenie
-<center><math>\displaystyle (z,q)\, \mid \! \Longrightarrow ^{w_{1}a}(z_{1},\ldots z_{k},q_{k+1})</math></center>
-co kończy dowód indukcyjny równoważności. Na jej podstawie, przyjmując  <math>\displaystyle q=q_{0},\: z=z_{0}  </math> ,
-otrzymujemy
-<center><math>\displaystyle (q_{0},z_{0},q)\mapsto^{*}_{G}w\, \Leftrightarrow \, (z_{0},q_{0})\, \mid \! \Longrightarrow ^{w}\, (1,q').</math></center>
-Uwzględniając, iż dla dowolnego stanu  <math>\displaystyle q  </math>  mamy w gramatyce  <math>\displaystyle G  </math>  prawo
-<math>\displaystyle v_{0}\rightarrow (q_{0},z_{0},q)  </math>  oraz że automat  <math>\displaystyle AS  </math>  akceptuje
-słowa przez pusty stos (stan  <math>\displaystyle q'  </math>  jest nieistotny), ostatnia równoważność
-kończy dowód twierdzenia.
-<math>\displaystyle \diamondsuit</math>   }}
----- dla dociekliwych - end ----
+<font color=red>ANIMACJA ja-lekcja10-w-anim2.jpg. Opis animacji w pliku
+ja-lekcja10-w-anim2-opis.</font>