Next: About this document ...
A nyelvtant először Chomsky normál alakra hozzuk és megszámozzuk a
szabályokat:
,
,
,
,
,
,
,
A tábla kitöltve:
A magyarázat hozzá:
az alsó sorba kerülnek azok a nemterminálisok, amikből az egy
darab terminális betűk kijönnek, azaz az ,
és
nemterminálisok.
A második sor kitöltése:
az első mezőbe egy olyan X nemterminális jöhetne, amiből az aa részszó
legenerálható, azaz, amire lenne
szabály.
Ilyen nemterminális nincs, ezért semmi sem kerül az első kockába.
A második kockába olyan jön, akire van
jobboldalú szabály,
ilyen nemterminális az A. Mivel az
szabály
jobboldalának első nemterminálisa az első sorban áll, ezért az A első
indexe az 1, a második index meg azért a 3, mert az
szabály sorszáma ez.
A következő két kocka azért üres, mert nincsen
jobboldalú szabály, az utolsó kockába pedig azért kerül B1,6,
mert van
szabály, ennek sorszáma 6 és a jobboldal
első szimbóluma, a
a táblázat első sorában van.
A harmadik sor kitöltése: Az első kockába olyan nemterminálisok
jöhetnének, amikre van X1X2 jobboldalú szabály, ahol X1
az 1. sor 1. kockájában van, X2 pedig a 2. sor 2. kockájában van vagy
X1 az 2. sor 1. kockájában van, X2 pedig az 1. sor 3. kockájában.
De egyik esetben sincsen ilyen nemterminális, vagyis ez a kocka üres.
D2,4 azért kerül a második kockába, mert van
szabály
és A a 2. sor 2. kockájában van,
pedig az 1. sor 4. kockájában.
A szabály sorszáma (4.) adja a második indexet, az első meg azt mutatja, hogy
az A-t hol kell keresni: a 2. sorban.
A másik lehetőség (amikor az abb betűket a és bb
leosztásban szeretnénk előállítani) nem vezet eredményre.
Mostantól csak azt írom, ahova kerül valami.
A negyedik sor első mezőjébe azért jut A1,2, mert van
szabály (2. számú szabály)
és
van az 1. sor elején és D van a 3. sor
2. kockájában.
Az ötödik sor első mezőjébe a D4,4 a
szabály
miatt kerül és azért mert A áll a 4. sor elején és
áll az 1. sor
5. mezőjében.
Az S4,1 -et a legtetejére az
szabály miatt vesszük be,
plusz még mert A a 4. sor elején van, B pedig a 2. sor 5. kockájában.
A visszakeresés: mivel S4,1 áll legfelül, ezért a levezetés
-tal kezdődik és tudjuk, hogy az A1,2
nemterminális a 4. sor elején áll. A táblázatot megnézve ezért a
levezetés
-ként folytatódik.
D2,4-et kifejtve tovább:
.
Innen A1,3-at és B1,6-ot kifejtve, majd a kalapos
betűket terminálisra írva kapjuk az aabbbc szót.
Next: About this document ...
Judit Csima
2000-04-13