Determinisztikus 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 determinisztikus véges állapotú gép vagy determinisztikus véges állapotú automata (angolul deterministic finite state machine vagy deterministic finite automaton, általánosan használt rövidítéssel: DFA) egy véges állapotú gép, ahol minden állapot–bejövő szimbólum párhoz egy és csakis egy másik állapotba való átmenet tartozik.

A DFA a szabályos nyelvek halmazába tartozó nyelvek felismerésénél használható, más nyelveknél nem alkalmazható.

A DFA 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). Amikor az utolsó bejövő szimbólum beérkezik, azt a gép állapotától függően vagy elfogadják vagy visszautasítják.

A DFA-t tekinthetjük egy speciális Turing-gépnek, amely nem tudja az olvasófejet mozgatni, és csak előre képes mozgatni a szalagját.

Formális meghatározás[szerkesztés | forrásszöveg szerkesztése]

Egy DFA a következő ötössel írható le: (S, Σ, T, s, A), ahol

  • (S) az állapotok véges halmaza
  • (Σ) az ábécének nevezett véges halmaz
  • (T : S × Σ → S) az átmeneti függvény
  • (sS) a kezdő állapot
  • (AS) az elfogadó állapotok halmaza.

Legyen M egy DFA, amelynél M = (S, Σ, T, s, A), és X = x0x1 … xn a Σ ábécéből alkotott string. M elfogadja az X stringet, ha létezik S-ben az átmenetek r0, r1, …, rn sorrendje a következő feltételekkel:

  1. r0 = s;
  2. ri+1 = T(ri, xi), minden i = 0, …, n-1-re;
  3. rnA.

Amint azt az első feltétel mutatja, a gép az s állapotból indul. A következő feltétel szerint az egyes állapotok változása a T átmeneti szabályok szerint következik be. Az utolsó feltétel szerint ha X utolsó szimbólumának beolvasása után a gép A állapotban van, akkor X-et elfogadja, ellenkező esetben visszautasítja.

Az automata által elfogadott stringek halmaza egy nyelvi forma, az a nyelv, amelyet a DFA felismer.

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

A következő példa azt mutatja, hogyan tudja az M automata, amely egy bináris ábécével dolgozik, felismerni azt, hogy a bemeneti stringben páros számú 0 karakter van-e.

M = (S, Σ, T, s, A), ahol

  • Σ = {0, 1},
  • S = {S1, S2},
  • s = S1,
  • A = {S1}, és
  • A T átmeneti függvényt a következő állapotátmeneti tábla határozza meg:
0
1
S1 S2 S1
S2 S1 S2

M állapotdiagramja :

DFA.png

Jól látható, hogy az S1 állapot felel meg annak a helyzetnek, amikor páros számú 0 érkezett eddig a bemeneten, míg S2 jelzi a páratlan számú 0-t. Egy 1-es érkezése az bemenetre nem változtatja meg az automata aktuális állapotát, és amikor a bemenet elfogyott, az automata állapota mutatja, hogy a bejövő string páros számú 0-t tartalmazott, vagy nem.

M nyelve egy szabályos nyelvvel írható le, egy adott szabályos kifejezés segítségével:

1^*(01^*01^*)^* \,\!

Előnyei és hátrányai[szerkesztés | forrásszöveg szerkesztése]

A DFA az egyik leggyakorlatiasabb modell a számítógép-tudományban, mert végrehajtási ideje lineárisan függ a bemenő string hosszától, álladó a helyigénye, ha egy online algoritmussal szimulálják a DFA-t. Adott két DFA-ra létezik olyan hatékony algoritmus, amely képes az általa felismert nyelvben felismerni az unió, a komplementerképzés és a különbségképzés műveleteket. Léteznek hatékony algoritmusok annak meghatározására, hogy egy DFA felismer egy stringet, egy DFA felismer minden stringet vagy mindkét DFA felismeri ugyanazt a nyelvet, és lehet olyan DFA-t találni, amely egy adott nyelvet minimális számú állapottal ismert fel. Ez az úgynevezett minimálautomata.

Más oldalról a DFA-k erősen korlátozott teljesítményt nyújtanak az általuk felismert nyelvekben, valamint nem alkalmasak olyan problémák megoldására, amelyekhez emlékezetre van szükség.

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

  • Michael Sipser: Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 053494728X. Section 1.1: Finite Automata, pp. 31–47. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
  • 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]