Języki, automaty i obliczenia/Wykład 11: Automat ze stosem

{LEMAT O POMPOWANIU DLA JĘZYKÓW
BEZKONTEKSTOWYCH. Własności języków bezkontekstowych. Problemy rozstrzygalne}

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

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

(o pompowaniu) Dla dowolnego języka bezkontekstowego $L \subset A^{*}$ istnieją liczby naturalne $N, M \geq 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} | \leq 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 \geq 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} | \leq 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} | \leq 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 \geq 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 \geq 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

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 \geq 1} \in ℒ_{2}

L (G_{2}) = {a^{n} b^{m} c^{m} : n, m \geq 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 \geq 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.

♢

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 \geq 1} \cup {a^{n} b^{m} c^{m} d^{n} : m, n \geq 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.

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 | \leq 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 | \leq N$ .

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

c a r d L = ℵ_{0} ⟺ \exists w \in L : N < | w | \leq 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 | \leq 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} | \leq | w_{1} u w_{2} | \leq 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 11: Automat ze stosem

Spis treści

Lemat o pompowaniu

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

Jednoznaczność języków bezkontekstowych

Problemy rozstrzygalne algorytmicznie

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia