Nicht-deterministische Automaten enthalten Übergänge, die den Automaten dazu veranlassen, zwischen mehreren Möglichkeiten zu wählen oder spontan von einem Zustand in einen anderen zu wechseln. Er ist also nicht mehr strikt an einen genau spezifizierten Ablauf gebunden.

Hier ein einfaches Beispiel eines nicht-deterministischen Automaten: Er nimmt eine Zahl von 0 bis 10 entgegen (das | steht für ODER).

                                 #=============#
                           /---->| Primzahl    |
                   2|3|5|7/      #=============#
                         /
    #================#--/  0|2|4|6|8|10  #=============#
    | Warte auf Zahl |------------------>| gerade Zahl |
    #================#--\                #=============#
                         \
    0|1|2|3|4|5|6|7|8|9|10\      #=============#
                           \---->| Ganzzahl    |
                                 #=============#

Zuerst einmal ist es einfach, die Funktionsweise dieses Automaten zu verstehen: Enthält er beispielsweise eine 9, so hätte er die Möglichkeit, zum Status "Ganzzahl" zu springen, die anderen States kommen nicht in Frage. Die Zahl 5 jedoch könnte auch zu "Primzahl" führen.

Nicht-Deterministische Automaten haben aber eine entscheidende (faszinierende) Eigenschaft: Dieser Automat hat im Gegensatz zu manchen Computerprogrammen den Vorteil, dass er theoretisch in mehreren Zuständen gleichzeitig sein kann. Wenn beispielsweise die Zahl 8 eingegeben wird, so wird die Anfrage, on die Zahl eine Ganzzahl war, wahr ergeben, denn der Automat würde sich nun im Status "gerade Zahl" befinden. Ebenso würde aber die Anfrage "gerade Zahl"? positiv ausfallen. Ein nicht-deterministischer Automat hat also die Fähigkeit, mehrere Möglichkeiten gleichzeitig zu speichern. Dies entspricht nicht gerade dem normalen menschlichen Vorstellungsvermögen, theoretisch ist dies jedoch möglich. Dazu dann gleich mehr.

Wenn eine 2 eingegeben wird, so würden alle drei Zustandsanfragen positiv ausfallen. Die Zahl Pi würde in keinen der drei Zustände passen und somit stets negativ ausfallen.

Eine gute Anwendungsmöglichkeit für nicht-deterministische Automaten ist das Parsen eines Strings. Die Zeichen des Strings werden dabei einzeln in den Automaten eingespeist, und dieser sagt dann zum Schluss, ob der String gültig war (Man sagt, er befindet sich in der durch den Automaten gegebenen Sprache) oder nicht oder sogar, um was für eine Art von String es sich handelt.

Um die Sache mit den Sprachen genauer zu verstehen, hier die allgemein üblichen Schreibweise für die Definition der akzeptierten Wörter:

*	beliebig viele
( )	Klammerung
|	oder
e	Abkürzung für epsilon: der leere String

Hier ein paar Beispiele:

01*	0, 01, 011, 0111, 01111, ...
(01)*	e, 01, 0101, 010101, 01010101, ...
10|01	10, 01
0*|1*	e, 0, 00, 000, 0000, ... , 1, 11, 111, 1111, ...
1*(0|1)11*	01, 11, 101, 111, 011, 111, 1101, 1111, 1011, 1111, ...

Zu jeder so konstruierbaren Sprache gibt es einen zugehörigen Automaten.

In diesem Zusammenhang wird hier noch der sogenannte Acceptor (Akzeptierer) eingeführt. Dies ist nichts anderes als die "Einfärbung" eines Status. Befindet sich der Automat nach dem Durchlaufen des gesamten Strings in einem solchen eingefärbten Acceptor, so war der String gültig, andernfalls nicht. Im folgenden werden Acceptoren komplett mit # umrahmt, um sie von den normalen States zu unterscheiden.

Folgendes Beispiel zeigt einen Automaten für die Sprache 10* (= 1, 10, 100, 1000, ...), Start ist im Status s0:

  #====#          ######---\
  | s0 |---------># s1 #   | 0
  #====#    1     ######<--/

Zurück zur Sache mit den mehreren Zuständen gleichzeitig: Man definiert folgendes: Es werde ein String in einen gegebenen Automaten gesteckt. Falls es auch nur eine Möglichkeit gibt, dass der Automat in einem Acceptor landet (ganz am Schluss), dann wird der ganze String akzeptiert (ist gültig, bzw ist in der Sprache).

Dadurch sind ganz erstaunliche Dinge möglich. Hier nur ein Beispiel:

Man möchte alle Strings akzeptiert haben, die an der n-letzten Stelle eine 1 haben. Das Problem ist, dass ein String nur von vorne durchlaufen werden kann, man weiss also (nach normaler Denkweise) nicht, wo sich diese n-letzte Stelle befindet (man sieht ja nicht, wann das Ende kommen wird). Die Aufgabe ist zwar deterministisch lösbar, allerdings nur mit exponentiell vielen States. Ein deterministische Automat kommt da mit nur n+1 States aus (Start bei s0):

    /---#====#   1    #====#  0|1   #====#  0|1             ######
0|1 |   | s0 |------->| s1 |------->| s2 |------> . . . ---># sn #
    \-->#====#        #====#        #====#                  ######

Wie gesagt ist das Kriterium des Akzeptierens eines Strings, dass mindestens eine Möglichkeit existiert, dass der Automat in einem Acceptor landet. Da der einzige Acceptor der rechteste ist, muss das letzte Zeichen des Strings somit auf den rechtesten Übergang fallen (Man könnte auch sagen, dass das letzte Zeichen zum rechtesten Status führt). Was die jeweils vorherigen Zustände hervorruft, ist somit ebenfalls bestimmt (einfach immer das vorherige Zeichen). In den Status s1 gelangt man also nur mit dem n-letzten Zeichen, und zwar nur, wenn dieses 1 ist. Alle anderen Zeichen, die vor diesem Zeichen kommen, bleiben im Status s0 stecken.

Es ist verständlich, dass diese Überlegungen etwas verwirrend sind. Tatsächlich kann man solche nicht-deterministische Automaten auch (erst?) simulieren. Leider führt die Simulation wiederum zu exponentiell vielen (virtuell hinzugefügten) Zuständen, wodurch das Ganze also vorerst nur ein Denkspiel bleibt.