10. ábra: “3-as típusú grammatika algoritmusai” ablak
A 10. ábrán látható felületen lehetőségünk nyílik a 3-as típusú grammatikákra tanult algoritmusok működését megfigyelni.
Elérés
Az “Új grammatika/automata” ablakban, ha a megadott grammatika 3-as típusú és megnyomjuk a “Tovább az algoritmusokhoz!” feliratú gombot, akkor jutunk el ehhez
a felülethez.
Gombtípusok
1.típus: grammatika gombok. Velük a kialakult grammatikát tudjuk megtekinteni. Ezek az alap, a megszorított és a normálforma feliratú gombok.
2.típus: algoritmus gombok. Egy ilyen gombra kattintva elindíthatjuk a kívánt algoritmust. Ezek a gombok az ε-mentesítés, a Láncmentesítés, a Hosszredukció és az Új nyelvtani jel $-hoz feliratúak.
3.típus: lejátszó gombok. Általuk az átalakításhoz szükséges algoritmusok
az átalakításhoz szükséges sorrendben, egymás után lefutnak. Az előbb említett gombok neve Alap
Megsz. lejátszás, Alap
Nf. lejátszás és Megsz
Nf. lejátszás.
4.típus: “Automaták algoritmusai” ablak megnyitása.
5.típus: a grammatika mentéséért felelős gomb.
Algoritmusok
Epszilon-mentesítés: Konstruálunk egy kezdő H halmazt, amely azon nyelvtani jeleket tartalmazza, amelyekből közvetlenül levezethető az ε. Ezután a szabály-rendszerből elhagyjuk az ε levezetéseket, valamint átalakítjuk azokat a szabályokat, amelyekben H halmazbeli nyelvtani jel szerepel: az eredeti szabály megtartása mellett, felveszünk olyan új szabályt, amelyben a H halmazbeli nyelvtani jel már nem szerepel. Ha a szabály több H-beli nyelvtani jelet is tartalmaz, a nyelvtani jelek elhagyását minden lehetséges kombinációban el kell végezni. Majd bővítjük a H halmazt azon nyelvtani jelekkel, melyeknek van olyan levezetése, ami csupa H-beli nyelvtani jelekből áll, és ismételjük a szabályok átalakításának algoritmusát. Ezt mindaddig kell folytatni, amíg a H halmaz bővül. Ha az S kezdőszimbólum eleme a H halmaznak, akkor megnézzük, hogy a szabályok jobb oldalán szerepel-e ez az S nyelvtani jel.
Ha szerepel, akkor új szabály bevezetése szükséges: S’
S | ε. Ekkor az S’ lesz az új kezdőszimbólum. (KES szabály felvétele)
Amennyiben nem szerepel egyetlen levezetésben sem az S kezdőszimbólum, úgy bevezetünk egy új jobboldalt, az S
ε -t.
Láncmentesítés: Meghatározzuk minden Q nyelvtani jelhez azt a halmazt, amely olyan nyelvtani jelekből áll, amelyek a Q nyelvtani jelből közvetetten levezethetőek lánc szabályokon keresztül. Lánc szabálynak nevezzük azt a szabályt, amelynek bal és jobb oldala is csak egy nyelvtani jelet tartalmaz. Minden Q nyelvtani jel halmazképzése után minden X halmazbeli elemre vegyük a belőlük levezethető Y szabályokat. Ezután
a Q-ból levezethető X nyelvtani jel helyére írjuk be a belőle levezethető Y szabályokat. Az algoritmust addig ismételjük, amíg a szabályrendszerünk nem tartalmaz láncszabályokat.
Redukálás: Első lépés a Zsákutca mentesítés: azon nyelvtani jelek elhagyása, melyekből nem vezethető le terminális szó. Második lépés az összefüggővé alakítás: azon nyelvtani jelek elhagyása, amelyek nem szerepelhetnek a kezdőszimbólumból levezetett mondatformákban.
Hosszredukció: Azt a grammatikabeli szabályt, amely több mint két jelből
(két vagy több terminális jel, legfeljebb egy nyelvtani jellel zárva) áll, átalakítjuk vele ekvivalens, a 3-as normál formának megfelelő szabály-sorozattá. Ez úgy történik, hogy vesszük az első jelet az átalakítandó szabályból, ami mögé beillesztünk egy olyan nyelvtani jelet, ami vagy a meglévő nyelvtani jelek közül kerül ki, vagy egy új nyelvtani jel lesz. Ez attól függ, hogy a grammatikában szerepel-e olyan nyelvtani jel, ami
az átalakítandó szabályból az első jel levételével keletkezett új szabályt levezeti (és csak ezt vezeti le).
Új nyelvtani jel bevezetése az ε levezetéséhez: Megkeressük azon jobboldalakat, amelyek csak egy darab terminálisból állnak. Ezen szabályokhoz bevezetünk egy új nyelvtani jelet - amely csak az ε -t vezeti le - és a terminális mögé “ragasztjuk”.