Endlicher Automat


Endliche Automaten sind ein zentrales Konzept der Informatik. Sie eignen sich besonders gut zur Modellierung autonomer IT-Systeme – wie z. B. Roboter oder Steuerungen.

Als ‚Endlicher Automat‘ wird ein Modell bezeichnet, in dem das Verhalten eines Systems als eine endliche Menge von Zuständen beschrieben wird. Der Übergang von einem Zustand in einen anderen wird dabei von Bedingungen (wie z. B. Ereig­nissen) ausgelöst, auf die jeweils eine Aktion folgt. Endliche Automaten werden daher auch „Zustandsmaschinen“ genannt.

Endliche Automaten haben in der Infor­matik bei der Entwicklung von Compilern (‚Übersetzern‘) für Computersprachen eine wichtige Rolle gespielt. In der Theoretischen Informatik wird das Konzept des Endlichen Automaten verwen­det, um einige fundamentale Aussagen über Algorithmen zu formulieren und zu bewei­sen. Wer mehr über die theore­tischen Hintergründe wissen möchte, dem sei als Lektüre das Grundlagen­werk der Automatentheorie von Hopcroft und Ullman empfohlen [1].

Prinzipiell lässt sich jedes informationstechnische System – ein MP3-Spieler, ein Smartphone, ein Computer – als Endlicher Automat beschreiben bzw. ‚modellieren‘. Dabei entsteht ein sehr klarer Überblick über das (gewünschte) Systemverhalten. Sehr kom­plexe Systeme versucht man zunächst auf einer höheren Abstraktionsebene als Endlichen Automa­ten zu modellieren, damit das Systemver­halten als Ganzes noch überschaubar bleibt.

Will man ein Programm zur Lösung einer bestimmten Aufgabenstellung entwickeln, sollte man sich immer zunächst (mindestens im Kopf, besser auf Papier) ein Modell von der Lösung machen, anstatt gleich mit der Programmierung zu beginnen. Sonst läuft man leicht Gefahr, ein chaotisches Programm mit viel Flickwerk zu erzeugen – das man möglicherweise schon wenig später selbst nicht mehr so recht durchschaut.

Um eine Problemlösung als Endlichen Automaten zu modellieren, muss man zunächst alle Zustände definieren, die das zu entwickelnde System annehmen soll, und in denen es einen ‚Auslöser‘ (= Bedingung) erwartet, um in einen anderen Zustand überzugehen und eine Aktion zu veranlassen. Einer dieser Zustände wird als Startzustand S des Endlichen Automaten festgelegt, in dem sich das System direkt nach der Aktivierung befindet. Damit die Lösung auch irgendwann endet, sollte der Automat einen Endzustand E besitzen. Anders als beim Startzustand kann der Automat über mehrere Endzustände verfügen.

Dargestellt wird ein Endlicher Automat entweder grafisch als Zustandsübergangsdiagramm oder als –tabelle. Im Zustandsübergangsdiagramm werden Zustände als Kreise und Übergänge als Pfeile (mit Bedingung) zum jeweiligen Folgezustand dargestellt; in einer Zustandsübergangstabelle ordnet man allen Zuständen für jede Bedingung einen Folgezustand zu. Außerdem ist festzulegen, ob eine Aktion vor, während oder nach einem Zustandsübergang ausgeführt wird. Je nach Aufgabenstellung kann die eine oder die andere Variante angemessener sein. Im Zustandsübergangsdiagramm lässt sich diese Unterscheidung darstellen, indem die Aktion oben oder unten im Zustands-Kreis oder am Übergangs-Pfeil eingetragen wird. In einer Zustandsübergangstabelle notieren wir die Aktion für alle drei Varianten in Klammern hinter dem Eintrag des Folgezustands, in oder vor dem die Aktion ausgeführt werden soll.

[1] John E. Hopcroft, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitäts-theorie. Addison-Wesley, 1990.
[2] Ferdinand Wagner, Ruedi Schmuki, Thomas Wagner, Peter Wolsten-holme: Modeling Software with Finite State Machines. A Practical Approach . CRC Press, 2006.