Összehasonlítás

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

--- szakdoli:redukalas [2015/11/24 10:53] – [A redukálás folyamata] peter
+++ szakdoli:redukalas [2015/12/04 13:49] (aktuális) – [A szabály hosszredukció alkalmazása] peter
@@ Sor 1: / Sor 1: @@
 [[szakdoli:menu|Szakdolgozat: Véges automaták és reguláris nyelvek kapcsolata]] \\
-====== Redukálás ======
+====== Szabály hosszredukció ======
+===== A szabály hosszredukció elmélete =====
+Legyen G = (N, Ʃ, P, S) 3-típusú nyelvtan. Ekkor van olyan G' = (N', Ʃ, P', S) 3-típusú nyelvtan, amelyre L(G) = L(G'), és P'-ben minden szabály A → aB vagy A → a alakú (A → λ is megengedett), ahol A, B ∈ N és a ∈ Ʃ.<sup>5</sup>
+===== A szabály hosszredukció alkalmazása =====
+A szabály hosszredukció végrehajtásához adjuk hozzá a "Feldolgozás műveletei" listához a „Szabály hosszredukció” elemet. A szabály végrehajtása a „feldolgozás” gomb megnyomására történik. A szabály lefutása során kiírja az indulási állapotot és a lefutás utáni eredmény állapotot.
+===== A szabályredukció folyamata =====
+A szabály hosszredukció algoritmus megkeresi az összes olyan szabályt, amelynek jobb oldalán minimum 3 tagból áll. Ezeket a szabályokat alakítja át úgy, hogy a minden szabály amely a szabály halmazban található maximum 2 tagból álljon.\\ \\
+A megtalált minimum 3 tagból álló szabályokat először leellenőrzi, hogy valamely 2 tetszőleges tagját tudja-e helyettesíteni egy már meglévő olyan szabállyal, amely bal oldali NT tagjához csak pontosan egy azonos szabály tartozik. A műveletet addig folytatjuk, amíg minden szabály maximum 2 tagból áll.\\ \\
+=== Példa az átalakításra ===
+Átalakítandó szabály halmaz:
+  A → SAB | a    <-- Az itt lévő 3 tagú szabályt át kell alakítani! Az utolsó 2 tagot (AB) helyettesítjük a létrehozott új szabállyal (C)
+  B → S | b
+  S → λ | AB
+Átalakított szabály halmaz:
+  A → SC | a
+  B → S | b
+  S → λ | AB
+  C → AB
-===== A redukálás alkalmazása =====
-A redukálás végrehajtásához kapcsoljuk be a „Redukálás” kapcsolót. A szabály végrehajtása a „feldolgozás” gomb megnyomására történik. A szabály lefutása során kiírja az indulási állapotot és a lefutás utáni eredmény állapotot.
-===== A redukálás folyamata =====
-A redukálás folyamán a szabály halmazból eltávolítjuk azokat a szabályokat, amelyeket a kezdő állapotból kiindulva nem tudunk elérni, így nincsenek használva a feldolgozás során.\\ \\ Figyelem: A következő egyszerűsített feltételezést nem jelenthetjük ki: van olyan NT elem a szabályok között, amelyik egyik szabály jobb oldalán sem található. Ha találunk ilyent, akkor a hozzá tartozó összes szabályt törölhetjük.\\ \\ Az előző mondatok azért nem állják meg a helyüket, illetve rossz redukáláshoz vezetnének, mert ha van két NT szabály amelyek egymásra mutatnak, de nincsenek kapcsolatuk a kezdő szimbólummal, akkor Ők az előző feltételezés szerint megmaradnának, de egy valóságos redukálás esetén mindkettőt törölni kell!\\ \\
-=== Példa a szabály alkalmazására ===
-Kiinduló szabály halmaz:\\
-  A → Aa | b | a
-  B → b | a
-  C → a                <-- jól látható, hogy ezen szabály (S kezdő szimbólum esetén) nincs használva
-  S → ASB | b | a
-Eredmény szabály halmaz:
-  A → Aa | b | a
-  B → b | a
-  S → ASB | b | a