The Butterfly Project

“Automaták algoritmusai” ablak

11. ábra: “Automaták algoritmusai” ablak

A 11. ábrán látható felületen lehetőségünk nyílik az automatákra tanult algoritmusokat megfigyelni.

Elérés

1. Kattintsunk a “3-as típusú grammatika algoritmusai” ablakban az Automata gombra
2. Kattintsunk az “Új grammatika/automata” ablakban, az Automata Varázsló vagy a Megnyitás részfelületen a “Tovább az algoritmusokhoz!” feliratú gombra, miután megadtunk minden szükséges információt.

Gráf csúcstípusai

Kezdőállapot: teli kör színe világos bőr (wheat)
Végállapot: körben a teli kör
Közönséges csúcs: teli kör színe világos barna (tan)

Gombtípusok

1.típus: automata gombok. Velük a kialakult automatát tudjuk megtekinteni háromféle módon: formálisan, táblázat útján és gráfos ábrázolással. Ezek a gombok a PNDA (Parciális, nem determinisztikus automata), a PDA (parciális determinisztikus automata), a DA (determinisztikus automata) és a MIN DA (minimális, véges, determinisztikus automata).
2.típus: algoritmus gombok. Egy ilyen gombra kattintva elindíthatjuk a kívánt algoritmust. Ezek a gombok a đ kiterjesztése halmazokra, a Hibaállapot meghatározása és a Minimalizáció feliratúak.
3.típus: a felette szereplő automata mentéséért felelős gomb

Algoritmusok

Automata determinisztikussá tétele: Akkor beszélünk nem determinisz-tikus automatáról, ha az automatának van olyan állapota, amelyből egy adott bemenő jel olvasása után nem egyértelmű az automata viselkedése: két vagy több állapot közül “választhat”, ahová tovább lép, A determinisztikussá tevő algoritmusban áttérünk egy olyan automatára, melynek állapotai a nemdeterminisztikus „A” automata állapotainak részhalmazai. A kiinduló állapot az eredeti kiinduló állapotot tartalmazó egy elemű halmaz, elfogadó állapotai pedig azok az állapothalmazok lesznek, melyek tartalmazzák az eredeti automata valamely elfogadó állapotát. Az állapot átmenet függvény egy részhalmazon (jelölje Q) és egy t bemenő jelen lesz értelmezve. Értékét úgy számíthatjuk ki, hogy vesszük az eredeti állapot átmenet függvény értékeinek unióját minden Q-beli állapot és t bemenő jel esetén. A determinisztikus automata állapotait a kezdőállapotot tartalmazó halmazból indulva úgy határozzuk meg, hogy kiszámítjuk az előbbiek szerint az állapot átmenet függvény értékét, és amikor egy új, eddig nem szereplő részhalmazt kapunk, akkor azt (és csak azt) felvesszük a determinisztikus automata állapotai közé. Az algoritmust addig folytatjuk, amíg új állapotot már nem kapunk. Ekkor az előbbiek szerint meghatározzuk a végállapotokat.

Hibaállapot meghatározása: Ez az algoritmus a parciális automatát alakítja át nem parciálisra. Sokszor egy adott állapot esetén nincs megadva az automata működése minden lehetséges bemenetre. Ez azért van, mert csak a helyes szavak elfogadásának lépéseit ábrázolja az automata. A hiányzó átmenetek tehát a hibás szavak esetei. Ekkor az automatához hozzáveszünk egy új, “hibaállapotot”, meghatározzuk azon állapotokat, amelyekre nem volt megadva átmenetfüggvény. Majd ezen átmenetek mindegyikéhez a hibaállapotot definiáljuk.

Automata minimalizálása: Első lépés az automata összefüggővé alakítása úgy, hogy elhagyjuk azokat az állapotokat, amelyek nem érhetők el a kezdőállapotból egyetlen lehetséges működés esetén sem. Második lépés az, hogy meghatározzuk az ekvivalens állapotokat, amiről bővebb leírás az irodalomjegyzék [1] számú pontjában található. Majd ezen állapot osztályokon adjuk meg az automata állapot átmenet függvényét.

 

The Butterfly Project
Váraljai Fruzsina