Nemdeterminisztikus véges állapotú gép

A Wikipédiából, a szabad lexikonból.

Ezt a szócikket át kellene olvasni, ellenőrizni a szövegét, tartalmát. További részleteket a cikk vitalapján találhatsz.

A számítógép-tudományban, a nemdeterminisztikus véges állapotú gép vagy a nemdeterminisztikus véges állapotú automata, angol terminológá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.

[szerkesztés] Á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 átmeneti függvény alapján megváltozik (vagy ugyanaz marad).

A gép nem determinisztikus, mivel lehetséges olyan belső állapota, amikor az adott belső állapotból egy bejövő szimbólum hatására több lehetséges állapot következhet, illetve létrejön állapotváltás bemenő szimbólum nélkül is. Például, az automata az 1-es állapotban van, és a követekező bejövő szimbólum az a, de az a beolvasás nélkül a 2-es állapotba kerül, és 3-as állapotba kerül a bejövő a hatására, azaz egy helyes belső állapotból nem determinált egyértelműen a következő állapot.

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.

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 valamelyike kerül, azaz: csak akkor utasítja vissza a stringet, ha nem kerül elfogadó állapotba.

[szerkesztés] 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 átmeneti függvény
s₀ a kitüntetett kezdeti (vagy indító) állapotok halmaza (s₀ ⊆ 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, 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 ∈ (Σ ∪{ε}), és létezik az állopotoknak az r₀,r₁, ..., r_n, r_i ∈ S sorrendje, valamint teljesülnek a következő feltételek:

r₀ ∈ s₀
r_i ∈ T(r_i-1, x_i ), minden i = 1, ..., n
r_n ∈ 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 átmenetei szabályok határozzák meg, attól függően, hogy szimbólumot, vagy üres stringet olvasott be. Amikor az autonmata beolvasta az utolsó szimbólumot, és elfogadó állapotban van, akkor mondhatjuk, hogy az NFA elfogadta a stringet, ellenkező esetben pedig visszautasította azt.

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 konstruálással történik, ami oda vezet, hogy exponenciálisan megnő a belső állapotok száma.

[szerkesztés] 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 működésére.

Létrehozzuk azonknak a lehetséges állapotoknak a halmazát, egy adat struktú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. Minde 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 mármelyikbe kerülhet.

[szerkesztés] Példa

A következő példában az M FNa 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 átmeneti függvényt a következő állapot átmeneti tábla írja le:

	0	1	ε
S₀	{}	{}	{S₁, S₃}
S₁	{S₂}	{S₁}	{}
S₂	{S₁}	{S₂}	{}
S₃	{S₃}	{S₄}	{}
S₄	{S₄}	{S₃}	{}

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^*)^*)$

[szerkesztés] Források

Michael Sipser. Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 053494728X. 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