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.

Általános ismerteté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

Egy NFA a következő 5-össel írható le: (S, Σ, T, s₀, 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.
• s₀ a kitüntetett kezdeti (vagy indító) állapotok halmaza (s₀ $\subseteq$ S)
• (A $\subseteq$ 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, s₀, A), és X az Σ ábécéből alkotott string. M elfogadja az X stringet, ha létezik X-nek egy x₁x₂ … x_n formájú megvalósítása, x_i $\in$ (Σ \{ε}), és létezik az állapotoknak az r₀,r₁, …, r_n, r_i $\in$ S sorrendje, valamint teljesülnek a következő feltételek:

1. r₀ $\in$ s₀
2. r_i $\in$ T(r_i-1, x_i ), minden i = 1, …, n
3. r_n $\in$ 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

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 $n-1$ másolatát. Az automata új állapotként ezek közül bármelyikbe kerülhet.

Példa

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, s₀, A) ahol

• Σ = {0, 1},
• S = {S₀, S₁, S₂, S₃, S₄},
• s₀ = {S₀},
• A = {S₁, S₃}, és
• A T átmenetfüggvényt a következő állapot átmenettábla írja le:

	0	1	ε
S0	{}	{}	{S1, S3}
S1	{S2}	{S1}	{}
S2	{S1}	{S2}	{}
S3	{S3}	{S4}	{}
S4	{S4}	{S3}	{}

M állapotdiagramja a következő:

A diagramon az S₀-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 {S₂, S₁} állapotokat, a másik az {S₃, S₄} á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:

$(1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})$

Források

• 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

Lásd még

• Determinisztikus véges állapotú gép
• Turing-gépek