Next: About this document ...
A táblázatok:
Semmi = 0 b = 1 d = 2
v = 3 u = 4 v = 5
u = 6 v = 7 e = 8
Magyarázat a táblázathoz:
A 0. halmazba betesszük az egyetlen mondatszimbólum-baloldalú szabályt az
előírt alakban és kész.
Az 1. halmazba alapítóként bekerül a
szabály, mert
az első betű a szóan b. Mivel a pont mögött nemterminális (D) áll,
beveszük a másik két szabályt, kifejtve így a pont mögött álló nemterminálist.
A 2. csoport alpítóelemei a
és
szabályok, mert
mindkettőt egy 1. halmazbeli elemből kapjuk a d átlépésével.
További elemek ide nem kerülnek, mert nincsen nemterminális közvetlenül
pont után és véget sem ért egy szabály sem.
A 3. csoportba alapítóként kerülnek a
és a
szabályok, mindkettőben a v-t léptük át. Az első szabályban D áll a
pont után, ezért bevesszük a
és a
szabályokat. A
szabály miatt pedig a következőt tesszük:
az 1. halmazban megkeressük ezen szabály ``előzményét'', a
szabályt és megkeressük azt a szabályt, aki miatt ez az előzmény
bekerült az 1. halmazba, ez most a
szabály. Ebben átlépjük
a D nemterminálist a ponttal és a 3. halmazba berakjuk a
szabályt is. Itt viszont S áll a pont után, tehát be kell vennünk a két
utolsó szabályt is.
A 4. csoport alapítótagjait úgy kapjuk, hogy megnézzük, melyik 3. halmazbeli
szabályban áll u a pont mögött. Két ilyen szabály van, ezek lesznek az
alapítóelemek a 4. halmazban és egyben egyedüliek is, mivel további
teendő nincs velük.
Az 5. halmaz hasonlóan jön, mint a hogy a 3. jött:
alapítóként bekerülnek az
és
szabályok. Az első miatt bevesszük az
és
szabályokat. Az
szabály miatt pedig a 3.
halmazban megkeressük ``előzmény''-szabályt, vagyis az
-at
és megkeressük azt a szabályt is, aki miatt ez az előzmény
bekerült az 3. halmazba, ez a
szabály. Ebben átlépjük
az S nemterminálist a ponttal és végül az 5. halmazba
berakjuk a
szabályt is.
A 6. halmaz alapító és egyben egyedüli elemeit hasonlóan kapjuk, mint a 4.
halmaz esetén.
A 7. halmazba alapítóként bekerül az
és
szabály. Az első miatt bekerül még az
és az
szabály is. Az
szabály miatt az 5.
halmazban megkeressük az
szabályt, majd azt ami miatt
ez oda bekerült, ez az
szabály. Emiatt az
-t
berakjuk a 7. halmazba, de ennek megint a végén van a pont. Így
megkeressük a 3. halmazban az
-at
és a
szabályt. Ez utóbbiban az S-t átlépve, berakjuk a 7.
halmazba a
szbályt is.
A 8. halmaz egyetlen alapító eleme az
lesz és
további elem nem is jön be.
Mivel az utolsó halmazban van olyan elem, ami a 0.-ban is volt, azzal az egy különbséggel, hogy
a pont most nem alöl, hanem hátul áll, a szó generálható a nyelvtannal.
A táblázatokból visszakereséssel jön a levezetési fa: visszanézzük, hogy melyik
szabály miért került be a táblákba.
Hátulról kezdjük: az utolsó táblában a
a 7. táblában
levő
miatt jött be.
A
szabály azért került be, mert ugrottuk az S-t, azt meg
azért tettük, mert az
szabály végére értünk, annak meg azért értünk
a végére, mert az
szabálynak a végére értünk.
Satöbbi, satöbbi...
Így visszajutunk és közben építjük a fát. Mire az elejére érünk, az első táblához,
addigra teljes lesz a fa.
Next: About this document ...
Judit Csima
2000-04-14