Készítsen egy teljesen definiált determinisztikus automatát az alábbi ábra alapján! (NFA csúcsokkal S, A, B, C). A megoldásnál a mozgások táblázatát kell megadni.
Eredeti NFA rajza
graph LR
Start(( )) --> S((S))
S -- "a, b, c" --> S
S -- "b" --> A((A))
S -- "c" --> C((C))
A -- "c" --> B(((B)))
C -- "c" --> B(((B)))
Megoldás menete (Logika)
Kezdőállapot: Az új automata kezdőállapota az eredeti kezdőállapota: {S}.
Átmenetek vizsgálata: Vizsgáld meg, hogy az aktuális halmazból (pl. {S}) az 'a' jelre hova jutunk az eredetiben. Ha S-ből 'a'-ra A-ba és B-be is lehet menni, az új állapot {A, B} lesz.
Új állapotok: Minden újonnan keletkező halmazt ({A, B}, {C, S}, stb.) vegyél fel új állapotként a táblázatba, és vizsgáld meg azokra is az összes bemeneti jelet.
Teljes definiáltság: Ha egy halmazból egy jelre sehova nem vezet út, vezess be egy "csapda" állapotot (Ø vagy ∅), amiből minden jel önmagába mutat.
Végállapotok: Minden olyan halmaz végállapot lesz az új automatában, amely tartalmazza az eredeti automata legalább egy végállapotát.
Felkészülés más ábrákra
Ha az automata gráfja változik:
Mindig módszeresen haladj: addig írd az új sorokat, amíg minden keletkezett halmaznak nincs megvizsgálva az átmenete.
A halmazokban az elemek sorrendje nem számít ({A, B} ugyanaz, mint {B, A}).
Ne felejtsd el a csapda állapotot, ha a feladat "teljesen definiált" automatát kér!