Determinisztikus véges állapotú gép

A Wikipédiából, a szabad lexikonbó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, az a gép állapotától függöen vagy elfogadásra vagy visszautasításra kerül.

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

[szerkesztés] Formális meghatározás

Egy DFA 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 × Σ → S) az átmeneti függvény
(s ∈ S) a kezdő állapot
(A ⊆ S) az elfogadó állapotok halmaza.

Legyen M egy DFA amelynél M = (S, Σ, T, s, A), és X = x₀x₁ ... x_n a Σ ábécéből alkotott string. M elfogadja az X stringet, ha létezik S-ben a átmenetek r₀,r₁, ..., r_n sorrendje a követekező feltételekkel:

r₀ = s
r_i+1 = T(r_i, x_i), minden i = 0, ..., n-1
r_n ∈ A.

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 elfogadott, ellenkező esetben visszautasított.

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

[szerkesztés] Példa

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 = {S₁, S₂},
s = S₁,
A = {S₁}, and
A T átmeneti függvényt a következő állapot átmeneti tábla határozza meg:

	0	1
S₁	S₂	S₁
S₂	S₁	S₂

M állapot diagrammja :

Jól látható, hogy az S₁ állapot felel meg annak a helyzetnek, amikor páros számú 0 érkezett eddig a bemeneten, míg S₂ 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^*)^* \,\!$

[szerkesztés] Előnyei és hátrányai

A DFA az egyik leggyakorlatiasabb modell a 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 algoritussal szimulálják a DFA-t. Adott két DFA-ra létezik olyan hatékony algoritmus, amely képes az álatala felismert nyelvben felismerni az unió, a komplemens é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ény nyújtanak az általuk felismert nyelvekben, valamint nem alkalmasak olyan problémák megoldására, amelyekhez emlékezetre van szükség.

[szerkesztés] Források

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