Ez a dokumentum egy előző változata!
Szakdolgozat: Véges automaták és reguláris nyelvek kapcsolata
Üres szó lemma (λ szabályok eltávolítása)
A szabály alkalmazása
A programban található egy kapcsoló („Üres szó lemma szabály alkalmazása”), amely bekapcsolásával a létrehozott szabályhalmazt át tudjuk alakítani olyan szabályhalmazzá, amely maximum 1 db üres szó szabályt tartalmaz, mégpedig az S→λ szabály és ekvivalensen megegyezik az általa generált nyelv az eredeti szabályhalmaz által generált nyelvel.
A szabály folyamata
Ha egy adott nyelvben szerepel egy olyan szabály, amely üres szó-t (λ) tartalmaz, akkor a nyelvi szabály rendszert át lehet alakítani úgy, hogy olyan szabályt kapjunk amely nem tartalmaz üres szót és ekvivalens az eredeti szabállyal. A következőben ismertetek egy algoritmust, amely a programban be van építve, és eltávolítja a nyelvi szabályból az üres szó elemeket.
- Első lépésben azonosítjuk azokat a szabályokat, amelyek tartalmaznak üres szót (λ). Ezeket elválasztjuk azoktól amelyek nem tartalmaznak üres szót.
- Az üres szót nem tartalmazó szabályok képezik az új szabály halmaz alapját.
- Az azonosított szabályokból azokat amelyek A→λ formátumúak a rendelkezésre álló szabályokban behelyettesítjük mint üres karaktert (azaz töröljük a nemterminális elemet). Pl. A→λ; S→Aa esetén: S→a szabály kapunk.
- Ha egy szabályban több azonos nemterminális is szerepel, akkor külön-külön végezzük el a törlést és permutációban is. Pl.: A→λ; S→AaA; esetén: S→aA; S→Aa; S→a képződik.
- Ha több nemterminálisnak is van λ szabálya, akkor külön-külön elvégezzük a helyettesítést és utána egymás kombinációjában is végrehajtjuk ugyanezt. Pl.: A→λ; B→λ; S→AaB; esetén: S→aB; S→Aa; S→a képződik.
- Ha a szabályok feldolgozása közben az S→λ szabály előkerül valahol, akkor a kész szabályrendszerhez hozzá kell adni ezt a szabályt, mivel a nyelv által generált szavak között az üres szó-t is létre kell hozni, tehát szükség van erre a szabályra!
- Az összes üres szó szabály feldolgozása után ha az eredményhalmazban az átalakítást követően megint keletkezik üres szó szabály, akkor a folyamatot megint végrehajtjuk egészen addig, amíg nem kapunk olyan eredményt, amelyben már nincs üres szót trtalmazó szabály.
