Deterministische Endliche Automaten

Einführung

Wir wollen uns nun ein einfaches Maschinenmodell ansehen, mit dem man bestimmte Wörter erkennen kann. Das Ganze ist zwar inspiriert von echten Schaltkreisen, und man kann anhand dessen auch theoretisch Maschinen bauen, ist aber ein rein formales Konstrukt.

Zunächst überlegen wir uns, dass eine Maschine ein Wort am Sinnvollsten Zeichen für Zeichen einliest und verarbeitet. Wenn ein Zeichen eingelesen ist, muss sich irgendetwas in der Maschine verändern, das heißt, eine Maschine hat irgendeinen Zustand. Das heißt, das Einlesen eines Zeichens führt eine Maschine von einem Zustand in einen anderen Zustand über.

Gehen wir der Einfachheit halber davon aus, dass eine bestimmte Maschine nur endlich viele Zustände hat, und benennen wir diese Zustände mit Zahlen $1,\ldots,n$. Das Einfachste, was so eine Maschine beim Einlesen eines Zeichens tun kann ist, entscheiden, zu welchem Zustand sie Springen soll. Man kann sich einen so einfachen Zustand also so vorstellen:

TODO

    +------a1-------->
    |
   (n)-----a2-------->
    |      ...
    |
    +------an-------->

wobei $n$ die Nummer des Zustandes ist, und die $a_i$ die Zeichen des endlichen Alphabets sind. Die Pfeile zeigen dabei jeweils entweder wieder auf Zustände, oder "ins Leere". Eine Maschine, die sich aus mehreren solchen einfachen Zuständen zusammensetzt, nennt man einen (deterministischen endlichen) Automaten.

Ein sehr einfacher endlicher Automat ist zum Beispiel gegeben durch

TODO

         A
         |
         1
         |
   ---->(1)---0--->(2)---0--->
         A          |
         |          |
         +----1-----+

Der Einfachheit halber lässt man die Pfeile, die "ins Leere" zeigen, weg:

TODO

   ---->(1)---0--->(2)
         A          |
         |          |
         +----1-----+