Ugrás a tartalomhoz

deterministic finite-state automaton

A Wikiszótárból, a nyitott szótárból


Főnév

deterministic finite-state automaton (tsz. deterministic finite-state automatons)

  1. (informatika) determinisztikus véges állapotú automata

A Deterministic Finite-State Automaton (röviden: DFA, magyarul: determinista véges állapotú automata) egy formális modell, amely egy adott bemeneti karakterláncról (string) képes eldönteni, hogy az egy adott nyelvhez tartozik-e vagy sem. A DFA az automataelmélet egyik alapfogalma, és szoros kapcsolatban áll a reguláris nyelvekkel.


🧠 Alapgondolat

A DFA egy olyan gép, amely:

Minden pillanatban egy állapotban van, és egy adott bemeneti karakter alapján egyetlen következő állapotba lép tovább.

Nincs több választás — minden bemenetre egyértelmű, hogy mi történik.


🧾 Formális definíció

Egy DFA egy 5-ös tuple:

M = (Q, Σ, δ, q₀, F)

ahol:

Jelölés Jelentés
Q Az összes állapot véges halmaza
Σ A bemeneti ábécé (karakterek halmaza)
δ Az átmenetfüggvény: δ(q, a) → q'
q₀ A kezdőállapot, ahol indulunk
F Az elfogadó állapotok halmaza (F ⊆ Q)


🧮 Működési elv

  1. A gép indul az q₀ állapotból.
  2. Egyesével beolvassa a bemenet karaktereit.
  3. Minden karakterre a δ függvény alapján lép egy másik állapotba.
  4. Ha a bemenet végére érve egy elfogadó állapotban (q ∈ F) van, akkor elfogadja a szót, különben elutasítja.


🔁 Példa

Nyelv: Minden szó, ami pontosan két darab a betűt tartalmaz (ábécé: {a, b})

DFA állapotok:

Állapot Jelentés
q0 még nem láttunk a-t
q1 láttunk 1 a-t
q2 láttunk 2 a-t (elfogadó állapot)
q3 több mint 2 a → elutasító állapot

Átmenetek (δ):

Állapot bemenet Következő állapot
q0 a q1
q0 b q0
q1 a q2
q1 b q1
q2 a q3
q2 b q2
q3 a/b q3

Elfogadó állapot: q2


📦 Alkalmazások

Terület Példa
Fordítók Lexikai elemzés (pl. tokenek felismerése)
Szövegfeldolgozás Regex motorok mögött
Hálózatok Protokoll-állapotok kezelése
Játékfejlesztés NPC viselkedési logika modellezése
Digitális áramkörök Szinkron automata viselkedésmodellezés


✅ Tulajdonságai

Tulajdonság DFA
Determinisztikus? ✅ Igen
Véges számú állapot? ✅ Igen
Nondeterminizmust tartalmaz? ❌ Nem
Átváltható reguláris kifejezésre? ✅ Igen
Támogat üres átmenetet (ε)? ❌ Nem
Átlagos futásidő O(n), ahol n a bemenet hossza


⚖️ DFA vs NFA

Tulajdonság DFA NFA
Egyértelmű átmenet ✅ ❌ több lehetséges
Üres átmenet (ε) ❌ ✅
Bonyolultság Gyorsabb futás Egyszerűbb tervezés
Átalakítható másikká Igen Igen

Fontos: minden NFA-nak van megfelelő DFA-ja (bár lehet exponenciálisan több állapottal).

🧪 C++ vázlat – DFA osztály

class DFA {
    int currentState;
    unordered_map<int, unordered_map<char, int>> transition;
    int startState;
    unordered_set<int> acceptingStates;

public:
    DFA(int start, unordered_set<int> accepting) : startState(start), currentState(start), acceptingStates(accepting) {}

    void addTransition(int from, char input, int to) {
        transition[from][input] = to;
    }

    bool run(const string& input) {
        currentState = startState;
        for (char c : input) {
            if (transition[currentState].count(c) == 0) return false;
            currentState = transition[currentState][c];
        }
        return acceptingStates.count(currentState) > 0;
    }
};

✅ Összefoglalás

A DFA egy formális eszköz, amelyet reguláris nyelvek elfogadására használnak. Minden bemenetre determinált viselkedést mutat, így gyors és kiszámítható. Alkalmazása a számítástudomány és a nyelvfeldolgozás számos területén központi jelentőségű.

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=deterministic_finite-state_automaton&oldid=3495381”