Direkt zum Inhalt

Lexikon der Mathematik: nichtdeterministischer endlicher Automat

(non-deterministicfinite automaton, NFA), Automat mit endlich vielen Zuständen und einer Zustandsüberführungsfunktion, die einer Eingabe in einem Zustand mehrere Folgezustände zuordnen kann.

Der Automat ist damit bestimmt durch ein Tupel \(A=[Q,\sum, \delta, {Q}_{0},F]\), wobei Q die endliche Zustandsmenge und Σ das endliche Eingabealphabet sind, δ als Zustandsüberführungsfunktion jedem qQ und a ∈ Σ eine Teilmenge von Q als mögliche Nachfolgezustände zuordnet, Q0 als Teilmenge von Q die Menge möglicher Anfangszustände beschreibt, und F eine Menge von Akzeptierungszuständen ist.

Ein nichtdeterministischer endlicher Automat akzeptiert ein Wort a1ak über dem Alphabet δ, falls es eine Folge q0qk von Zuständen gibt, für die q0Q0, qkF und für alle i ∈ {0,…,k − 1} jeweils qi+1δ (qi, a) ist. Die Menge der von einem nichtdeterministischen endlichen Automaten akzeptierten Wörter ist immer eine reguläre Sprache. Zu jedem nichtdeterministischen endlichen Automaten kann ein dieselbe Sprache akzeptierender deterministischer endlicher Automat konstruiert werden, der möglicherweise wesentlich mehr Zustände hat. Für einen endlichen Automaten mit Ausgabe kann diese analog zur Zustandsüberführungsfunktion nichtdeterministisch gestaltet werden. Siehe auch endlicher Automat.

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