Ö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/11/22 20:04] – peter
+++ szakdoli:uresszo [2015/12/04 13:51] (aktuális) – [A szabály alkalmazása] peter
@@ Sor 2: / Sor 2: @@
 ====== Ü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 "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.
 ===== 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.\\
+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.\\
+. 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.:
-- Az üres szót nem tartalmazó szabályok képezik az új szabály halmaz alapját.\\
+  B → λ
-- 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.\\
+. Az üres szót nem tartalmazó szabályok képezik az új szabály halmaz alapját. Pl.:
-- 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.\\
+  S → Ba
-- 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.\\
+ezeket a szabályokat kell kibővíteni az új szabályokkal.\\ \\
-- 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 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:
-- 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     <-- 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