Felhasználói eszközök

Eszközök a webhelyen


szakdoli:zsakutca

Szakdolgozat: Véges automaták és reguláris nyelvek kapcsolata

Zsákutca mentesítés

A zsákutca mentesítés alkalmazása

A szabály hosszredukció végrehajtásához adjuk hozzá a „Feldolgozás műveletei” listához a „Zsákutca mentesíté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 zsákutca mentesítés folyamata

A zsákutca mentesíté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 zsákutca mentesítéshez 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 zsákutca mentesíté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
szakdoli/zsakutca.txt · legutóbbi módosítás: – Szerkesztő: peter