Nemdeterminisztikus véges állapotú gép
A számítógép-tudományban a nemdeterminisztikus véges állapotú gép vagy a nemdeterminisztikus véges állapotú automata, angol terminológiával a nondeterministic finite state machine vagy nondeterministic finite automaton (NFA) egy véges állapotú gép ahol bármelyik állapot–bejövő szimbólum párhoz több következő állapot is tartozhat.
Tartalomjegyzék
Általános ismertetés[szerkesztés]
Az NFA egy bejövő szimbólumokból álló stringgel dolgozik. Minden egyes bejövő szimbólum hatására a gép állapota az adott átmenetfüggvény alapján megváltozik (vagy ugyanaz marad). Az utolsó szimbólum feldolgozása után az NFA akkor, és csak akkor fogadja el a stringet, ha az automata a néhány elfogadó állapot valamelyikébe kerül, azaz: csak akkor utasítja vissza a stringet, ha nem kerül elfogadó állapotba.
A gép nem determinisztikus:
- Lehetséges olyan belső állapota, amiből a beolvasott szimbólum hatására több lehetséges állapot egyikébe mehet át.
Például, az automata az 1-es állapotban van, és a következő bejövő szimbólum az a. Az a beolvasása nélkül a 2-es állapotba kerülne, de a bejövő a hatására 3-as vagy 4-es állapotba kerül. Azaz egy helyes belső állapotból nem determinált a következő állapot még adott input esetén sem.
- Létrejöhet állapotváltás bemenő szimbólum nélkül is.
A bejövő szimbólum nélküli állapotváltozást epszilon átmenetnek nevezik, és általában a görög ε betűvel jelölik.
Formális meghatározás[szerkesztés]
Egy NFA a következő 5-össel írható le: (S, Σ, T, s0, A), ahol
- (S) az állapotok véges halmaza
- (Σ) az ábécének nevezett véges halmaz
- (T : S × (Σ \{ε}) → P(S)) az átmenetfüggvény. Ez lehet olyan reláció is, ami nem függvény.
- s0 a kitüntetett kezdeti (vagy indító) állapotok halmaza (s0 S)
- (A S) az elfogadó állapotok halmaza
ahol P(S) S hatványhalmaza, ε az üres string, és Σ a bemenő jelek ábécéje.
Legyen M egy NFA úgy, hogy M = (S, Σ, T, s0, A), és X az Σ ábécéből alkotott string. M elfogadja az X stringet, ha létezik X-nek egy x1x2 … xn formájú megvalósítása, xi (Σ \{ε}), és létezik az állopotoknak az r0,r1, …, rn, ri S sorrendje, valamint teljesülnek a következő feltételek:
- r0 s0
- ri T(ri-1, xi ), minden i = 1, …, n
- rn A.
Az automata a kezdő állapotból indulva olvassa a bejövő string szimbólumait, amelyek az adott ábécéhez kell, hogy tartozzanak. Az automata állapotát a T átmeneti szabályai határozzák meg, attól függően, hogy szimbólumot, vagy üres stringet olvasott be. Amikor az automata beolvasta az utolsó szimbólumot, és elfogadó állapotban van, akkor mondhatjuk, hogy az NFA elfogadta a stringet, ellenkező esetben pedig visszautasította.
Az automata által elfogadott stringek halmaza egy nyelvi forma, az a nyelv, amelyet az NFA felismer. Ez a nyelv egy szabályos nyelv.
Minden NFA-hoz található egy determinisztikus véges állapotú gép (DFA), amely ugyanazt a nyelvet fogadja el. Ebből következik, hogy lehetséges egy létező NFA-re olyan átalakítás, amelynek az eredménye egy DFA lesz, így megvalósítható egy (talán) egyszerűbb gépként. Az átalakítás általában a hatványhalmaz megkonstruálásával történik, ami oda vezet, hogy exponenciálisan megnő a belső állapotok száma.
Megvalósítása[szerkesztés]
Egy NFA több módon is megvalósítható:
- Egy vele ekvivalens DFA-vá alakítjuk át. Néhány esetben ez az automata méretének exponenciális növekedést okozza, de ennek nincs hatása a felismert nyelvre.
- Létrehozzuk azoknak a lehetséges állapotoknak a halmazát, egy adatstruktúra-halmazt, amelyekbe az automata kerülhet. Ha az utolsó szimbólum beolvasása után az automata állapota ezek között az állapotok között van, akkor elfogadta a stringet.
- Több választási lehetőséget engedünk meg. Minden olyan döntés, amelynek n lehetséges kimenete van, az jelenti, hogy az NFA-ban létre kell hozni a gép legfeljebb másolatát. Az automata új állapotként ezek közül bármelyikbe kerülhet.
Példa[szerkesztés]
A következő példában az M NFA működését vizsgáljuk, amely egy bináris ábécével dolgozik, így a bemeneti szimbólumok 0-k és 1-ek lehetnek csak.
M = (S, Σ, T, s0, A) ahol
- Σ = {0, 1},
- S = {S0, S1, S2, S3, S4},
- s0 = {S0},
- A = {S1, S3}, és
- A T átmenetfüggvényt a következő állapot átmenettábla írja le:
M állapotdiagramja a következő:
A diagramon az S0-ból induló, nem jelölt élek az epszilon átmenetek.
A fenti M gépet tekinthetjük két DFA uniójának: az egyik az {S2, S1} állapotokat, a másik az {S3, S4} állapotokat valósítja meg.
Az M gép nyelvét egy szabályos nyelv szabályos kifejezéseinek használatával a következőképen írhatjuk le:
Források[szerkesztés]
- Michael Sipser. Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.2: Nondeterminism, pp.47–63.
- Bach Iván. Formális nyelvek. Egyetemi tankönyv, második kiadás, Typotex Kiadó, 2001. 2.2. fejezet: Determinisztikus és nemdeterminisztikus véges automaták