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-----+

Einer der Zustände muss derjenige sein, in dem der Automat am Anfang, wenn noch garnichts eingelesen wurde, ist. Es hat sich eingebürgert, einen Pfeil der "aus dem Leeren" kommt, dafür zu benutzen:

TODO

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

Nehmen wir nun an, dieser Automat lese das Wort $0101$ ein. Das erste Zeichen ist $0$, und wir sind im Zustand (1). Der Zustand (1) hat einen Pfeil mit der Beschriftung $0$ zu Zustand (2). Das heißt, danach sind wir in Zustand (2).

Das nächste Zeichen ist $1$. Von (2) geht ein Pfeil mit der Beschriftung $1$ zum Zustand (1), das heißt, danach sind wir wieder im Zustand (1).

Das dritte Zeichen ist $0$. Analog zu vorhin gehen wir zu Zustand (2). Das vierte Zeichen ist wieder $1$, und wir gehen wieder zum Zustand (1).