Determinisztikus véges állapotú gép
A számítástudomá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 reguláris 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ésEgy 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
- (s ∈ S) a kezdő állapot
- (A ⊆ S) 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:
- r0 = s;
- ri+1 = T(ri, xi), minden i = 0, …, n-1-re;
- rn ∈ 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-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ésA 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:
| S1 | S2 | S1 |
| S2 | S1 | S2 |
M állapotdiagramja :
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:
Előnyei és hátrányai
szerkesztésA 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, állandó 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- 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
