Direkt zum Inhalt

Lexikon der Mathematik: deterministischer endlicher Automat

(engl. deterministic finite automaton, DFA), ein Automat mit endlich vielen Zuständen, einem einzigen Anfangszustand und deterministischer Übergangsrelation. Das heißt, daß zu jedem Zustand und jedem Eingabezeichen maximal ein Nachfolgezustand existiert.

Der Automat ist also bestimmt durch ein Tupel \begin{eqnarray}A=[Q,\Sigma, \delta, {q}_{0},F].\end{eqnarray}

Dabei ist Q die endliche Zustandsmenge, Σ das Eingabealphabet, δ die Überführungsrelation, d. h. eine partielle Abbildung von Q × Σ in Q. q0 ist der Anfangszustand, also ein Element aus Q, und F ist die Menge der Endzustände, also eine Teilmenge von Q. Der Automat A akzeptiert die Sprache \begin{eqnarray}{L}_{A}=\{w|w\in \Sigma *, \delta ({q}_{0},w)\in F\}.\end{eqnarray}

Dazu wird die Abbildung δ auf den Definitionsbereich Q × Σ fortgesetzt, indem für ϵ (das leere Wort) δ(q, ϵ) = q und für w = wx \begin{eqnarray}\delta (q,w)=\delta (\delta ({w}^{^{\prime} },q),x)\end{eqnarray} gesetzt wird. Ist dabei δ(w, q) oder δ(δ(w, q), x) undefiniert, so auch δ(q, w).

Eine von einem endlichen deterministischen Automaten akzeptierte Sprache ist immer eine reguläre Sprache.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos