Nemdeterminisztikus véges állapotú gép

A Wikipédiából, a szabad enciklopédiából

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.

Általános ismertetés[szerkesztés | forrásszöveg szerkesztése]

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). 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 | forrásszöveg szerkesztése]

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 átmeneti függvény. Ez lehet olyan reláció is, ami nem függvény.
  • s0 a kitüntetett kezdeti (vagy indító) állapotok halmaza (s0 \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, 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 \in (Σ \{ε}), és létezik az állopotoknak az r0,r1, …, rn, ri \in S sorrendje, valamint teljesülnek a következő feltételek:

  1. r0 \in s0
  2. ri \in T(ri-1, xi ), minden i = 1, …, n
  3. rn \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[szerkesztés | forrásszöveg szerkesztése]

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 azonknak 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 mármelyikbe kerülhet.

Példa[szerkesztés | forrásszöveg szerkesztése]

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

  • Σ = {0, 1},
  • S = {S0, S1, S2, S3, S4},
  • s0 = {S0},
  • A = {S1, S3}, és
  • A T átmeneti függvényt a következő állapot átmeneti tá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ő:

NFA.png

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:

(1^*(01^*01^*)^*) \cup  (0^*(10^*10^*)^*)

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]