Ez a dokumentum egy előző változata!
Tartalomjegyzék
Szakdolgozat: Véges automaták és reguláris nyelvek kapcsolata
Reguláris nyelv modul felépítése, kezelése
Megjegyzés: a rendszer megjegyzi az éppen szerkesztett szabályrendszer összes adatát, és egy újbóli lap betöltése vagy frissítés esetén megjeleníti azokat, nem vesznek el az adatok!
Terminális és nem terminális elemek kijelölése
A feladat kiírásakor peremfeltételként volt meghatározva, hogy először legyenek kijelölve a terminális (továbbiakban: T) és nem terminális (továbbiakban: NT) elemek, majd csak utána lehessen szabályokat alkotni. Ezért a felső részben megjelenítem a lehetséges T és NT elemeket. Ezzel korlátozva a szabályok létrehozásának lehetőségét. A T és NT sorokban található gombokra kattintva tudjuk kijelölni azt az elemet, amelyet használni szeretnénk a szabály felépítésekor. Az 'S' jelű NT elem automatikusan ki van jelölve, mivel Ő a kezdő elem. És bár a kezdő elem egyéb esetben tetszőlegesen választható az NT elemek közül, ebben a feladatban ezt fixáltuk és mindig kijelölt elemként jelenik meg! (törlése nem lehetséges)
Az ABC betűinek használatát kínálom fel a választáskor. A T elemek a kisbetűket, a NT elemek a nagybetűket tartalmazzák. 'A'-tól 'Z' karakterig listázom az angol ABC szerint a betűket. A karakterekből eltávolítottam az 'I', 'L' és 'O' karaktereket, mivel megtévesztőek lehetnek és a T és NT összekeverhetővé válhat egyes fontkészletek esetében. Ezzel a megszorítással 23 lehetőséget kínálok fel választásra az egyes csoportokban.
Szabály szerkesztése
A szabály szerkesztésében bevezettem bizonyos korlátozásokat:
- Csak a korábban kijelölt N és NT elemeket lehet felhasználni szabály készítésekor
- A bal oldalon csak 1 darab NT elemet lehet választani. Ezzel lekorlátoztam a létrehozható szabályok körét a Chomsky-féle 2-es és 3-as kategóriára.
Egy szabály elkészítésekor lehetőségünk van a legördülő választó mezőkből kiválasztani a szükséges T és NT elemet. Ha a felső részben engedélyezzük a használatát azaz kiválasztunk egy T vagy NT elemet, az azonnal megjelenik a legördülő listában található elemek között. Így bármikor változtathatunk a szükséges N és NT elemek között.
Figyelem: ha viszont törlünk egy engedélyezést a T vagy NT elemek között, akkor viszont azonnal törlődnek azok a szabályok a szabály halmazból amelyek tartalmazzák a most már nem engedélyezett T vagy NT elemet! Ezzel a megszorítással mindig konzisztens marad az elemek kijelölése a szabály halmazzal.
A szerkesztett szabály tagjainak számát lehet bővíteni vagy csökkenteni a '+' és '-' gombok segítségével. A minimális tagok száma egy. A maximális tagok száma nincs korlátozva.
Ha elkészültünk a szabály szerkesztésével, akkor a 'Szabály felvétele a szabályhalmazba' gomb segítségével tudjuk a szabály halmaz közé rögzíteni az új szabályt.
Lehetőségünk van egy adott szabályt törölni a szabály halmazból az adott szabály mellett található 'Törlés' gomb segítségével. Mivel egy-egy szabály szerkezete viszonylag egyszerű, ezért nem láttam szükségesnek egy módosítás funkció létrehozását. Módosítás esetén kövessük a következő folyamatot: törlés majd új szabály felvétele.
A 'Összes szabály törlése' gomb segítségével a teljes szabályhalmazt kitörölhetjük, és előröl kezdhetünk szabályhalmazt építeni.
Szabályhalmaz
A szabályhalmaz blokkban jelenik meg az aktuálisan szerkesztett szabályhalmaz összes szabálya. Ebben a blokkban ugyanaz a szabályhalmaz 3 különböző formátumban mutatjuk meg:
- Külön szabályonkénti felsorolás
- NT-vel csoportosított formátum
- Generatív nyelvtani formátum
A legvégén megjelenik a Chomsky-féle szabály kategória értéke is tájékoztatásnak.
Szabályhalmaz feldolgozásának műveletei
Ebben a blokkban tudjuk meghatározni azt, hogy a szabályhalmazon milyen átalakító algoritmusokat hajtsunk végre és azt milyen sorrendben tegyük meg. A rendszer azt biztosítja, hogy a kijelölhető átalakító algoritmusokat tetszőleges sorrendben végre lehet hajtani a szabály halmazon. A következő algoritmusok hajthatók végre:
- Önmaga szabályok eltávolítása
- Szabály többszörözés eltávolítása
- Üres szó lemma szabály alkalmazása
- Láncszabály mentesítés
- Zsákutca mentesítés
- Szabály hosszredukció
- Szabály konvertálása automatává
- Szabály szavainak előállítása
Ezek nagy része külön leírásban van részletezve, most az egyéb pontokat említjük csak.
Szabály konvertálása automatává
Ezen algoritmus kiválasztása a következő algoritmusok sorrendjében ajánlott:
- Láncszabály mentesítés
- Zsákutca mentesítés
- Szabály hosszredukció
- Szabály konvertálása automatává
A felsorolt szabályok készítik elő egy nyelvi szabályhalmazt olyan állapotba, hogy átalakítható legyen automata szerkezetté. Az algoritmus csak akkor engedi az átalakítást miután megvizsgálta, hogy minden egyéb feltételnek megfelel a szabályhalmaz. Az elfogadott szabály formátumok:
A→aA A→a A→λ
Az algoritmus végeredménye
- hibaüzenet: nem hajtható végre a konvertálás
- konvertálás végrehajtódott, át lehet lépni az automata modulra és megtekinthető a konvertált forma
Figyelem: Ezen pont alkalmazása sikeres végrehajtás esetén a jelenlegi automata törlésével/elveszésével jár!
Szabály szavainak előállítása
Lehetőség van arra, hogy megtekintsük a szabályhalmaz által generálható szavakat. Az előállításhoz több beállítás is tartozik, amelyeket a következő nagy pontban részletezek.
Figyelem: A szavak előállítása sokszor nagy számítási és idő igényű, ezért a beállításoknál csak akkor alkalmazzunk nagy értékeket ha már megbizonyosodtunk, hogy kis értékek mellett előállíthatók a szavak. Túl nagy érték esetén nagyon hosszú lefutási idővel lehet számolni!
Természetesen azt is megtehetjük, hogy a listában minden egyéb átalakító algoritmus után elhelyezzük ez az algoritmust, és megfigyeljük hogyan változnak az előállított szavak az egyes algoritmusok lefutása után.
Szabályhalmaz feldolgozási műveletek beállításai
Max mélység
A 'max. mélység' beállításával azt állíthatjuk be, hogy amikor a szabályhalmaz alkalmazásával a rendszer előállítja a lehetséges szavakat, akkor rekurzívan milyen mélységig kövesse a szabályokat a rendszer.
Pl. A→aA szabály esetében a végtelenségig lehetne 'a' karaktert tartalmazó szavakat előállítani. Ezen beállítással ez lekorlátozható pl. maximum 10 karakter hosszú szóra.
Max szó
A 'max. szó' beállításával azt állíthatjuk be, hogy mennyi legyen a maximálisan előállított szavak száma. Az előző pontban is említett példa esetében ez végtelen lenne, ennek a beállításnak az alkalmazásával ez lekorlátozható pl. maximum 1000 db szóra.
Max. futási idő
Lehetőségünk van korlátozni a szavak előállításának futási idejét másodpercben megadva. Így megakadályozhatjuk, hogy a túl hosszú futási idő miatt „lefagyás” jelenséget okozzunk a böngészőben. Természetesen ettől függetlenül elég nagy maximális értéket lehet beállítani, ami 86400 másodperc azaz 1 nap.
Szavak
A szavak előállításának végeredményét lehet szabályozni ezzel a kapcsolóval. A szavak megjelenési formátumát tudjuk szabályozni.
Egyedi szavak megjelenítése
A rendszer csoportosítja az egyes szavakat és minden szórt csak egyszer jelenít meg, és megmutatja a szó mellett a szó előfordulási mennyiségét is. A szavak ebben az esetben ABC sorrendben jelennek meg.
Minden szó megjelenítése
Minden egyes szót megjelenít a rendszer. Így előfordulhat, hogy egy szó többször is meg fog jelenni a listában. Ezzel a beállítással végig tudjuk követni a szavak előállítási sorrendjét (nincs sorba rendezés).
Szabályhalmaz eltárolása
Lehetőségünk van eltárolni egy adott nyelvi szabályhalmazt. Meg kell adni egy elnevezést, és a funkció aktiválásával a 'localStorage' rendszerben eltárolódik az aktuális szabályhalmaz összes adata.
Eltárolt szabályhalmazok kezelése
Az eltárolt szabályhalmazok listázódnak ki ezen menüpont alatt. Lehetőségünk van
Betöltés Az eltárolt adatok betöltésére Felülírás Az eltárolt adatok felülírására az aktuális szabályhalmaz adataival Törlés Az eltárolt adatok törlésére
A rendszer kiegészítésképpen megjegyzi a mentés dátumát és azt is kilistázza a felhasználó számára.
