Endlicher Automat

Einführung

Ein endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein mathematisches Modell eines Systems mit diskreten Ein- und Ausgaben. Diskret bedeutet, dass zu jedem Zeitpunkt nur eine Eingabe und eine Ausgabe verarbeitet wird. Es gibt eine endliche Anzahl ein Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einer endlichen Anzahl von Zuständen. Das Verhalten des Systems wird durch Zustände, Zustandsübergängen und Aktionen beschrieben.

Motivation

Computer, andere Maschinen oder Programme erscheinen im Alltag oft als eine Black Box, egal ob sie triviale oder schwierige Probleme lösen. Sie reagieren auf Eingaben, verarbeiten Informationen, ohne dass wir sehen, wie, und präsentieren eine Antwort bzw. eine Lösung. Manchmal scheinen Sie sogar ‚intelligenter‘ als Menschen zu sein, wenn sie gegen Schachweltmeister gewinnen, die 2,7 Billionen Nachkommastellen von n berechnen, einem sagen, was man als Nächstes kaufen möchte oder man mit einem Computer spricht, ohne es zu bemerken.

Doch das Verarbeiten der Eingaben ist weder Zauberei, noch (zumindest bis heute) intelligentes Vorgehen. Es sind Programme, die das Verhalten der Maschine bestimmen, und diese Maschinen lassen sich sogar durch einfach strukturierte Modelle wie den endlichen Automaten beschreiben. Die Einfachheit des Modells sollte aber nicht über deren Mächtigkeit hinwegtäuschen. Das Automatenmodell dient zum Beispiel der Zellforschung als probates Mittel, um das Verhalten von Zellen zu beschreiben, und auch die Hirnforschung greift bei der Beschreibung des Gehirns durch neurale Netze darauf zurück. Automaten findet man außerdem in zahlreichen Alltagssituationen vor: Fahrstühle, Ampel Waschmaschinen, Getränke, Fahrkarten- und Geldautomaten sind nur einige der vielen Maschinen, die von einem endlichen Automaten gesteuert werden.

Diese Automaten werden als endlich bezeichnet, weil die Menge der Eingaben, der Ausgaben und der Zustände, die sie durchlaufen, endlich sind. Folgt ein Automat folgender formalen Beschreibung, dann bezeichnet man diesen als Mealy-Automat.

Mealy-Automat

Definition

Für die Formalisierung des Automaten führt man zunächst die Ein- und Ausgabe ein. Sie werden als Eingabe und Ausgabealphabet bezeichnet. Der Begriff erklärt sich aus der Tatsache, dass Computer in der Regel Texte, also Zeichenfolgen eines Alphabets verarbeiten. Auch die Verarbeitung in einem Computer kann, da sie durch 0 und 1 repräsentiert wird, als die Verarbeitung von Texten angesehen werden.

Des Weiteren muss der Automat durch eine Zustandsmenge speichern, welche Eingaben bisher getätigt wurden. Die Zustände werden oft mit q0 ... qn bezeichnet. Mithilfe der Übergangsfunktion wird die zeitliche Abfolge der Ereignisse festgelegt. Die Übergangsfunktion gibt an, was welche Eingabe in jedem Zustand bewirkt. Neben der Übergangsfunktion gibt es noch die Ausgabefunktion, die angibt, welche Ausgabe durch die jeweilige Eingabe in einem Zustand ausgelöst wird. Die Übergangs- und Ausgabefunktionen werden tabellarisch oder grafisch als sogenannter Transitionsgraph oder Übergangsgraph dargestellt. Ein solcher Automat wird in der lnformatik als Mealy-Automat bezeichnet.

Formal definiert man einen Mealy-Automat als 6-Tupel A = {Q,s,∑,Ω, δ, λ}

Q ist eine nicht leere, endliche Menge von Zuständen

s∈Q ist der Startzustand

∑ ist ein nicht leeres, endliches Eingabealphabet

Ω ist ein nicht leeres, endliches Ausgabealphabet

δ:Qx∑ ->Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.

λ:Qx∑->Ω ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Ausgabe zuordnet.

Beispiel

Die Funktionsweise eines endlichen Automaten lässt sich leicht an einer einfachen Maschine wie einem Bonbonautomaten erläutern. Der Bonbonautomat lässt sich in seiner Funktionsweise wie folgt beschreiben. Die Eingabe besteht aus der richtigen Münze und dem Drehen des Hebels. Die Verarbeitung erfolgt im Inneren des Automaten und führt zur Ausgabe, dem Bonbon im Ausgabefach.

Die Eingabemöglichkeiten des Automaten sind begrenzt, es kommt jedoch auf die korrekte Reihenfolge an. Dreht man zuerst den Hebel und wirft dann die korrekte Münze ein, so erhält man nicht die gewünschte Ausgabe. Dazu wäre ein weiteres Drehen des Hebels erforderlich.

Bonbonautomat als Mealy Automat: A = {Q,s,∑,Ω, δ, λ}