(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 q ∈ Q und a ∈ Σ eine Teilmenge von Q als mögliche Nachfolgezustände zuordnet, Q₀ 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 a₁…a_k über dem Alphabet δ, falls es eine Folge q₀…q_k von Zuständen gibt, für die q₀ ∈ Q₀, q_k ∈ F und für alle i ∈ {0,…,k − 1} jeweils q_i+1 ∈ δ (q_i, 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.