Összehasonlítás

A kiválasztott és az jelenlegi változat között az alábbi különbségek fordulnak elő:

--- szakdoli:uresszo [2015/09/04 19:54] – [Üres szó lemma eltávolítása] peter
+++ szakdoli:uresszo [2015/12/04 13:51] (aktuális) – [A szabály alkalmazása] peter
@@ Sor 1: / Sor 1: @@
 [[szakdoli:menu|Szakdolgozat: Véges automaták és reguláris nyelvek kapcsolata]] \\
 ====== Üres szó lemma (λ szabályok eltávolítása) ======
-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.\\
+===== A szabály alkalmazása =====
-- 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.\\
+A "Feldolgozás műveletei" listába fel tudjuk venni az "Üres szó lemma szabály alkalmazása" opciót, 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.
-- Az üres szót nem tartalmazó szabályok képezik az új szabály halmaz alapját.\\
+===== A szabály folyamata =====
-- 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 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.\\ \\
-- 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.\\
+. 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. Pl.:
-- 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.\\
+  B → λ
-- 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 üres szót nem tartalmazó szabályok képezik az új szabály halmaz alapját. Pl.:
-- 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.\\
+  S → Ba
+ezeket a szabályokat kell kibővíteni az új szabályokkal.\\ \\
+. 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) és bővítjük az így keletkező új szabállyal a szabály halmazunkat. A fenti példákon elvégezve a műveletet:
+  S → Ba     <-- az eredeti szabályhalmaz hozadéka
+  S → a      <-- átalakításkor keletkező új szabály
+szabályhalmazt képződik eredményül.\\ \\
+. Ha egy szabályban több azonos nemterminális elem is szerepel, akkor külön-külön is elvégezzük a törlést és permutációban is. Pl.:
+  A → λ
+  S → AaA
+szabályhalmaz esetén:
+  S → aA
+  S → Aa
+  S → a
+szabályhalmaz képződik.\\ \\
+. Ha több nemterminálisnak is van λ szabálya, akkor az előző példához hasonlóan külön-külön is elvégezzük a helyettesítést és utána egymás kombinációjában is végrehajtjuk ugyanezt a műveletet. Pl.:
+  A → λ
+  B → λ
+  S → AaB
+szabályhalmaz esetén:
+  S → aB
+  S → Aa
+  S → a
+szabályhalmaz 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 az algoritmust megint végrehajtjuk egészen addig, amíg nem kapunk olyan eredményt, amelyben már nincs üres szót tartalmazó szabály. Ilyen eset lehet pl.:
+  S → Aa
+  A → B | aB
+  B → λ
+szabályhalmaz feldolgozása ('B' behelyettesítése) után kapott szabályhalmaz:
+  S → Aa
+  A → λ | a
+A keletkező szabályhalmazban megint van olyan szabály, amely λ tartalommal bír ezért az algoritmust újból lefuttatjuk a keletkezett szabály halmazon:
+  S → a
+  A → a