Datenverarbeitende Systeme:
Kapitel 2: Endliche Automaten

2.1 Was sind Automaten

Der Begriff Automat soll im Folgenden verwendet werden, um ein (geschlossenes) System und dessen innere Abläufe zu beschreiben. Einem Automaten werden feste innere Zustände und Zustandsübergangsfunktionen einbeschrieben. Ein innerer Ablauf sieht wie folgt aus: Eine Eingabe von außen führt von einem Zustand aus über eine Zustandsübergangsfunktion in einen zweiten Zustand.

Von endlichen Automaten spricht man, wenn der Automat einen oder mehrere Zustände hat, die als Endzustand angesehen werden können.

2.2 Endliche deterministische Automaten

Endliche deterministische Auotmaten sind wie folgt definiert:

• Es gibt genau einen Anfangszustand
• Von jedem Zustand S_n aus wird jede Eingabe x aus der Sprache L akzeptiert
• Eine Eingabe x führt von jedem Zustand S_n in genau einen Folgezustand S_n+1

Für Automaten zeichnet man gewöhnlich Graphen in folgender Form:

Dieser Automat erkennt Identifier für Variabeln, wie sie zum Beispiel Pascal verwendet. S₀ markiert den Startzustand, S₁ den Endzustand - erkennbar an der doppelten Umrahmung. Wird als erstes Zeichen eine Zahl eingegeben, dann wird in den Fehlerzustand verzweigt, der nichtmehr verlassen werden kann. Beliebige Buchstaben führen in den Endzustand, in dem beliebig viele weitere Zeichen eingegeben werden können. Der Identifier 16Zeiger wäre ungültig, Zeiger16 dagegen gültig. Versucht einmal zu erkennen, welches Wort der folgende Automat in einem beliebigen eingegebenen Text erkennen kann:

Fahrt mit dem Mauszeiger über das Bild, um die Lösung zu erfahren.

2.3 Endliche nichtdeterministische Automaten

Nichtdeterministische Automaten können bei einem Eingabesymbol x in mehrere Folgezustände übergehen. Sie können ebenso mehrere Ausgangszustände haben. Es muss nicht von jedem Eingabezustand aus auf jedes Eingabesymbol reagiert werden: Eingaben, die von einem Zustand nicht erkannt werden, führen zum Abbruch des entsprechenden Zustandes. Der Ausgangszustand wird nicht abgebrochen! Bricht der letzte Zustand ab, wird wieder beim Anfangszustand begonnen.

Es gibt verschiedene Möglichkeiten, wie ein Automat auf das Wechseln in verschiedene Folgezustände reagiert:

• Es sind alle Folgezustände gleichzeitig aktiv und reagieren autark auf weitere Eingaben
• Der Automat repliziert sich sooft, wie es Folgezustände gibt, und jedes Replikat nimmt einen der Möglichen Folgezustände ein
• Der Automat wählt einen Zustand s' aus allen Möglichen Folgezuständen und geht in diesen über

Für den Graphen bedeutet das: Von einem Zustand können mehere Pfade abzweigen, die auf die selbe Eingabe x reagieren. Der Folgende Zustandsgraph hat die selbe Funktion wie der obige.

Ich will die Arbeitsweise kurz erläutern, indem wir den Automaten mit der Eingabe AOOTTOBO füttern (ich spreche im Folgenden von Instanzen und meine damit die verschiedenen Zustände S, die der Automat annehmen kann):

Der Automat befindet sich zu Beginn im Zustand S₀. Das A bewirkt gar nichts, da der Startzustand nicht reagiert. Geben wir das erste O ein, so öffnet der Automat eine Instanz S₁ und hält gleichzeitig eine Instanz S₀ aufrecht (diese ist IMMER offen). Beim zweiten O bricht S₁ ab (die Instanz akzeptiert nur T!), aber von S₀ wird wieder in S₁ gewechselt. Analog geht es weiter, bis das letzte O eingegeben wird. Dann ist Zustand 4 erreicht. Welche Zustände sind offen, wenn das letzte O eingegeben wurde?

Antwort: S₀, S₁ und S₄

Es lässt sich zeigen, dass man für jeden nichtdeterministischen Automaten auch einen deterministischen Konstruieren kann. Dazu fasst man jede Kombination von Folgezuständen des nichtdeterministischen Automaten zu einem Zustand des Deterministischen zusammen. Dadurch vergrößert sich jedoch der Automat. Meist kann man jedoch den entstandenen Graphen noch weiter optimieren, indem man ein wenig darüber nachdenkt, wo redundante Übergänge vorliegen.