[ Pobierz całość w formacie PDF ]
poddrzewo T2 z korzeniem w wierzchołku v2 jest poddrzewem drzewa T1, zatem jeżeli T2
wywodzi słowo w, to możemy zapisać z = vwx, dla pewnych słów v, x. Zauważmy, że
vx = », gdyż w wierzchoÅ‚ku v1 zastosowana jest produkcja postaci A ’! BC oraz pod-
drzewo T2 jest poddrzewem drzewa z korzeniem w B lub z korzeniem w C wtedy druga
z tych zmiennych wywodzi pewne niepuste słowo v lub x. Aby zakończyć dowód twier-
dzenia wystarczy zauważyć, że w wierzchołku v2 możemy zaszczepić poddrzewo T1,
czyli zastosować produkcję użytą w v1 i postępowanie to iterować. W ten sposób otrzyma-
my drzewo wywodu słowa postaci uviwxiy " L dla i > 1. Z kolei, jeżeli w wierzchołku
v1 zastosujemy produkcję użytą w v2, to otrzymamy drzewo wywodu dla słowa uwy " L,
co kończy dowód.
Przykład 3.43 Pokażemy, że język
L = {aibici | i " N}
nie jest bezkontekstowy. Załóżmy, że L jest bezkontekstowy. Niech n oznacza stałą z lematu
o pompowaniu. Rozważmy słowo z = anbncn, |z| = 3n > v. Zatem z posiada rozkład
z = uvwxy oraz |vwx| d" n. Możliwe są następujące przypadki:
1. vwx = ak, k d" n,
2. vwx = akbl, k + l d" n,
3. vwx = bk, k d" n,
4. vwx = bkcl, k + l d" n,
5. vwx = ck, k d" n.
W każdym z powyższych przypadków otrzymujemy, że slowo z = uv2wx2y " L, co jest
¯
sprzeczne z tezą lematu. Rzeczywiście, w przypadku 1. mamy |z|b = |z|c = n oraz |z|a > n,
¯ ¯ ¯
w przypadku 2. mamy |z|c = n oraz |z|a > n lub |z|b > n. Pozostałe przypadki są
¯ ¯ ¯
analogiczne.
3.5. Operacje na językach bezkontekstowych 87
Zadanie 3.44 Udowodnij, że język
{anbmcndm | n " N}
nie jest bezkontekstowy.
3.5 Operacje na językach bezkontekstowych
Twierdzenie 3.45 Jeżeli mamy dwa języki bezkontekstowe K i L to językami bezkontek-
stowymi sÄ…: K *" L, KL, K".
Dowód:. Udowodnimy, że K" jest językiem bezkontekstowym. Dla operacji sumy i kon-
katenacji dowody są podobne. Załóżmy, że G = (V, T, P, S) jest gramatyką języka K
oraz S " V . Gramatyka G = (V *" {S }, T, P , S ) jest gramatyką języka K", gdzie
P = P *" {S ’! SS |»}. Aatwo pokazać, że L(G ) = (L(G))".
Jak pokazuje następny przykład, języki bezkontekstowe nie są zamknięte na przekrój.
Przykład 3.46 Języki
L1 = {anbncm | n, m " N}
oraz
L2 = {ambncn | n, m " N}
są bezkontekstowe, ale ich przekrój nie jest bezkontekstowy
L1 )" L2 = {anbncn | n " N}.
Zadanie 3.47 Udowodnij, że klasa języków bezkontekstowych nie jest zamknięta na uzu-
pełnienie.
Twierdzenie 3.48 Jeżeli język L jest bezkontekstowy, a R regularny, to przekrój L )" R
jest bezkontekstowy.
Dowód: Załóżmy, że L = L(A) jest akceptowany przez stan końcowy przez automat ze
stosem
A
A = (QA, £, “, ´A, q0 , Z, FA),
zaś R = L(B) jest akceptowany przez deterministyczny automat skończony
B
B = (QB, £, ´B, q0 , FB).
88 Rozdział 3. Klasa CF języków bezkontekstowych
C
OkreÅ›lamy automat ze stosem C = (QC, £, “, ´C, q0 , Z, FC), gdzie QC = QA × QB,
C A B
q0 = (q0 , q0 ), FC = FA × FB, oraz funkcja przejÅ›cia jest okreÅ›lona nastÄ™pujÄ…co: jeżeli
´A(qA, a, g) (pA, ³) oraz ´B(qB, a) = pB, to ´C((qA, qB), a, g) ((pA, pB), ³), oraz
jeżeli ´A(qA, », g) (pA, ³), to ´C((qA, qB), », g) ((pA, qB), ³). MówiÄ…c mniej formal-
nie automat ze stosem C symuluje równolegle działanie obu automatów A i B na słowie
wejściowym. Pamięć automatu C posiada dwa rejestry. W pierwszym rejestrze automat
C przechowuje bieżący stan automatu A, a w drugi stan automatu B. Jeżeli automat ze
stosem A wykonuje ruch bez czytania litery z wejścia, to współrzędna odpowiadająca sta-
nowi z automatu B nie zmienia się. Słowo wejściowe jest zaakceptowane przez C wtedy i
tylko wtedy, gdy jest zaakceptowane przez oba automaty A i B.
Zadanie 3.49 Udowodnij, że język
{wcw | w " {a, b}"}
nie jest bezkontekstowy.
3.6 Parsery
Mamy gramatykę G i słowo w, jak stwierdzić, czy w " L(G). Parsery to programy, które
rozwiązują takie problemy. Jeżeli gramatyka G opisuje poprawne zdania w języku natu-
ralnym, to parser stwierdza, czy dane zdanie jest poprawnie zbudowane. Jeżeli gramatyka
G opisuje język programowania, to parser stwierdza, czy dany program jest poprawnie
zbudowany. Często parsery robią więcej; nie tylko stwierdzają, czy w " L(G) ale także,
znajdują wywód (lub drzewo wywodu) słowa w w gramatyce G.
Aby zrozumieć jak działają parsery, rozważmy tak zwane drzewo słów wywodliwych
w gramatyce G. W korzeniu mamy symbol początkowy S. Jeżeli w wierzchołku x ma-
my sÅ‚owo ±, to wszystkie sÅ‚owa, które można wywieść w jednym kroku lewostronnego
wywodu znajdują się w synach wierzchołka x.
Przykład 3.50 Dla gramatyki
S ’! aSB | ab
początek drzewa wywodliwych słów przedstawiony jest na rysunku 3.7.
Nie należy mylić drzewa wywodliwych słów z drzewem wywodu. Drzewo wywodu przed-
stawia wywód jednego słowa, natomiast drzewo wywodliwych słów zawiera w sobie le-
wostrone wywody wszystkich słów w " L(G). Na podstawie twierdzenia 3.10 w drzewie
3.6. Parsery 89
S
aSb ab
aaSbb aabb
aaaSbbb aaabbb
Rysunek 3.7: Drzewo wywodliwych słów
wystarczy rozpatrywać lewostronne wywody. W liściach drzewa znajdują się wszystkie
słowa z L(G). Działanie najprostszych parserów oparte jest na algorytmach przeszukiwa-
nia drzew. Najprostsze algorytmy przeszukiwania drzew "w głąb" i "wszerz" nie działają
zbyt dobrze. Jeżeli słowo posiada wywód, to metoda przeszukiwania "wszerz" znajdzie go.
Jeżeli jednak słowo nie ma wywodu, to metoda ta będzie szukać w nieskończoność, po-
nieważ drzewo przeważnie jest nieskończone. Metoda przeszukiwania "w głąb" może nie
znalezć słowa, nawet jeżeli ono tam jest. Na przykład w drzewie z rysunku 3.7 algorytm
przeszukiwania w głąb pójdzie w nieskończoną lewą galąz i nigdy nie znajdzie słowa ab.
Dlatego parsery oprócz przeszukiwania stosują tak zwane obcinanie gałęzi. Na przykład
jeżeli parser szuka słowa aabb w drzewie z rysunku 3.7 i dojdzie do wierzchołka aaaSbbb,
to może dalej nie szukać w głąb ponieważ wiadomo, że wszytkie słowa niżej zaczynają się
od aaa. Obcinanie gałęzi jest skuteczne, jeżeli gramatyka jest w postaci normalnej Chom-
sky ego lub Greibach. W takich gramatykach każde następne słowo w wywodzie jest nie
krótsze od poprzedniego. Dlatego można obcinać gałęzie, które leżą poniżej słów dłuż-
szych od szukanego słowa w. Nawet jeżeli sprowadzimy gramatykę do postaci normalnej,
to naiwny algorytm przeszukiwania drzewa będzie działal w czasie wykładniczym. Można
tu zastosować programowanie dynamiczne i czas wyszukiwania wywodu sprowadzić do
czasu wielomianowego O(|w|3) (patrz 5.1).
Zadanie 3.51 Dla gramatyki z przykładu 3.2 narysuj początek drzewa wywodliwych słów
i przedyskutuj sposoby poszukiwania słowa aaab.
90 Rozdział 3. Klasa CF języków bezkontekstowych
3.7 Języki liniowe
Definicja 3.52 Gramatykę nazywamy liniową, jeżeli produkcje są postaci
"
" A ’! uBv, A, B " V, u, v " T ,
"
" A ’! w, A " V, w " T .
PrzykÅ‚ad 3.53 Gramatyka liniowa G = ({S}, {0, 1}, {S ’! 0S1 | 01}, S) generuje jÄ™zyk
{0k1k | k > 0}.
Gramatyka jest prawostronnie liniowa, jeżeli zawiera produkcje postaci A ’! uB, A ’!
w. Podobnie gramatyka jest lewostronnie liniowa, jeżeli zawiera tylko produkcje postaci,
A ’! Bu, A ’! w.
Twierdzenie 3.54 Klasa języków generowanych przez gramatyki prawostronnie liniowe
jest równa klasie języków regularnych.
Dowód:Pokażemy jak dla deterministycznego automatu skoÅ„czonego, A = (Q, £, ´, q0, F )
zdefiniować równoważnÄ… gramatykÄ™ G = (V, £, P, q0). Przyjmujemy jako zmienne stany
automatu, V = Q, a produkcje definiujemy w następujący sposób:
(p ’! aq) " P jesli ´(p, a) = q,
(p ’! ») " P jesli p " F
Indukcyjnie wzglÄ™dem dÅ‚ugoÅ›ci sÅ‚owa w " £+ można pokazać, że automat A przechodzi
[ Pobierz całość w formacie PDF ]