Endliche Automaten - Einführung

Eine Denksportaufgabe:

Ein Mann steht mit einem Wolf, einer Ziege und einem Kohlkopf am linken Ufer eines Flusses, den er überqueren will. Er hat ein Boot, das groß genug ist, ihn und ein weiteres Objekt zu transportieren, so dass er immer nur einen der drei mit hinübernehmen kann. Falls der Mann allerdings den Wolf und Ziege unbewacht an einem der Ufer zurückläßt, so wird der Wolf sicherlich die Ziege fressen. Genauso wird, wenn die Ziege und der Kohlkopf unbewacht zurückbleiben, die Ziege den Kohlkopf fressen.

Ist es möglich, den Fluss zu überqueren, ohne dass die Ziege oder der Kohlkopf gefressen werden?

Lösung:

Zur Umsetzung des Problems ist festzustellen, dass die aktuelle Information darin besteht, wer nach jedem Überqueren an den beiden Ufern steht. Es gibt 16 Teilmengen mit den Elementen Mann (M), Wolf (W), Ziege (Z) und Kohlkopf (K).

linkes Ufer	rechtes Ufer	erlaubter Zustand
0	MWZK	x
M	WZK	-
W	MZK	x
Z	MWK	x
K	MWZ	x
MW	ZK	-
MZ	WK	x
MK	WZ	-
WZ	MK	-
WK	MZ	x
ZK	MW	-
MWZ	K	x
MWK	Z	x
MZK	W	x
WZK	M	-
MWZK	0	x

Die "Eingaben" für das System sind die durchgeführten Aktionen. Der Mann kann den Fluss alleine überqueren (Eingabe m), mit dem Wolf (Eingabe w), mit der Ziege (Eingabe z) oder mit dem Kohlkopf (Eingabe k). Der Anfangszustand ist MWZK - 0 , und der Endzustand ist 0 - MWZK. Aus dem Anfangszustand MWZK - 0 kann man direkt höchstens in die Zustände WZK - M, WZ - MK, WK - MZ und ZK - MW gelangen, wobei aber nur der Zustand WK - MZ sinnvoll wäre. Mit ähnlichen Überlegungen kann man folgenden Übergangsgraphen (Transitionsdiagramm) aufstellen:

Jetzt ist es leicht zu sehen, dass es zwei gleichermaßen kurze Lösungen gibt, die man durch Suche nach Pfaden vom Anfangszustand zum Endzustand (das ist der mit dem Doppelkreis) finden kann. Es sind dies die Pfade zmwzkmz sowie zmkzwmz , die jeweils 7 Fahrten lang sind. Alle weiteren - unendlich viele - Lösungen enthalten nutzlose Zyklen.

Wo liegt nun der Vorteil dieser Darstellung?

Nun, ich denke das Problem ist so klar und übersichtlich gelöst, dass man bedenkenlos gegen jemand wetten würde, der behauptet, er habe eine Lösung mit 5 Fahrten gefunden. Viel wichtiger ist jedoch die Erkenntnis, dass sich alle Systeme mit endlicher Zustandsmenge auf ähnliche Weise beschreiben lassen. Wir haben eine Struktur gefunden, die weit über die Informatik hinausreicht. Der Beweis soll im folgenden angetreten werden.

So schön das Beispiel ist, so ist es doch ein Spezialfall für Systeme mit endlicher Zustandsmenge: Erstens gibt es nur einen Endzustand - im Allgemeinen sind es mehrere - und zweitens gibt es hier zufällig für jeden Übergang einen Übergang in umgekehrter Richtung, der mit dem gleichen Symbol markiert ist, was im Allgemeinen nicht der Fall sein braucht. Außerdem werden beim Übergang von einem zum anderen Zustand keine Ausgaben produziert, was im Allgemeinen durchaus vorkommen kann.

Ein endlicher Automat ist ein (mathematisches) Modell eines Systems mit diskreten Ein- und Ausgaben. Das System befindet sich in einem aus einer endlichen Anzahl von inneren Konfigurationen - sogenannten "Zuständen".

Definition und Arbeitsweise eines endlichen Automaten

Definition:

Ein endlicher Automat (EA) besteht aus

einer nichtleeren, endlichen Menge E von Eingabezeichen, dem Eingabealphabet
einer nichtleeren, endlichen Menge A von Ausgabezeichen, dem Ausgabealphabet
einer nichtleeren, endlichen Menge Z von Zuständen
einer Überführungsfunktion f_ü : ZxE --> Z, die jedem Paar aus aktuellem Zustand und Eingabe einen Folgezustand zuordnet
einer Ausgabefunktion f_a : ZxE --> A, die jedem Paar aus aktuellem Zustand und Eingabe eine Ausgabe zuordnet
einem ausgezeichneten Element s₀ aus Z, dem Anfangszustand

Arbeitsweise:

Der EA arbeitet in diskreten Schritten. Zu einem gewissen Zeitpunkt befinde er sich im Zustand z. Falls ein Eingabezeichen e vorhanden ist, liest er dieses beim nächsten Takt und geht in den Zustand z_neu = f_ü(z,e) über, wobei er das Zeichen a = f_a(z,e) ausgibt. Der Automat beginnt seine Arbeit definitionsgemäß im Startzustand s₀. Dieser Vorgang läßt sich verdeutlichen, wenn wir die für den Automaten vorgesehenen Eingaben auf einem Eingabeband, die von ihm erstellten Ausgaben auf einem Ausgabeband und seinen aktuellen Zustand sowie die Funktionen f_ü und f_a in einer Steuereinheit zusammenfassen:

Für solche Automaten, die man auch Transduktoren nennt, müssen wir jetzt allerdings fordern, dass bei jedem Takt der Lesekopf der Steuereinheit um einen Schritt nach rechts auf dem Eingabeband fortschreitet. Ebenso soll sich der Ausgabekopf verhalten.

lokal