logo

The Butterfly Project

Bevezetésnyil

Az alkalmazás

Rövid leírásnyil

Használati útmutató

Telepítés/Indítás

Futtatásnyil

Felületek

"Fő"nyil

"Új grammatika/automata"nyil

„2-es típusú grammatika algoritmusai”nyil

„CYK algoritmus"nyil

„3-as típusú grammatika algoritmusai”nyil

„Automaták algoritmusai”nyil

Algoritmusok felületenyil

Algoritmusok léptetésenyil

 

“3-as típusú grammatika algoritmusai” ablak

3asalg

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 nyil Megsz. lejátszás, Alapnyil Nf. lejátszás és Megsz nyil 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’ nyil 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 nyilε -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”.

 

The Butterfly Project
Váraljai Fruzsina