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:

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

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

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

        (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:

   ---->(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). Das Wort ist vollständig eingelesen.

Natürlich bringt es uns nicht viel, Wörter nur einlesen zu können. Was wir wollen, ist, dass der Automat eine Entscheidung trifft: Er kann ein Wort akzeptieren oder ablehnen. Fürs Akzeptieren definieren wir Endzustände, und sagen, wenn der Automat nach dem Einlesen des Wortes in einem Endzustand ist, dann gilt das Wort als akzeptiert. Endzustände stellen wir dar mit zwei Kreisen statt einem.

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

Das Wort $010$ wird zum Beispiel akzeptiert: Nach dem vollständigen Einlesen sind wir bei Zustand (2), welches ein Endzustand ist.

Wann immer ein Wort nicht akzeptiert wird, gilt es als abgelehnt. Das Wort $0101$ wird zum Beispiel abgelehnt: Am Ende ist man in Zustand (1), welcher kein Endzustand ist. Das Wort $011$ wird ebenfalls abgelehnt: nachdem wir $01$ eingelesen haben, sind wir in Zustand (1), aber der $1$-Pfeil von (1) zeigt ins Leere.

Beispiele

• Der folgende Automat erkennt genau $\varepsilon$:

   ---->((1))

• Der folgende Automat erkennt beliebig viele Wiederholungen von "abc":

   ---->((1))---a--->(2)---b--->(3)
          A                      |
          |                      |
          +----------c-----------+

• Der folgende Automat erkennt beliebige Folgen von $0$ und $1$ mit gerade vielen $1$-en:

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