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,∑,Ω, δ, λ}

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,∑,Ω, δ, λ}

Grafische Darstellung

Übergangsfunktion

Die Übergangsfunktion δ:Qx∑ ->Q ordnet jeder Kombination aus einem Zustand (erste Spalte) und einem Eingabezeichen (erste Zeile) einen Nachfolgezustand (Matrix) zu. Dies lässt sich sehr gut tabellarisch darstellen:

M: Münze einwerfen

H: Hebel drehen

B: Bonbon ausgeben

N: Keine Ausgabe

Gäbe es einen Endzustand, würde dieser in der Tabelle mit einem Stern kenntlich gemacht.

Beispiel Übergangsfunktion für den Bonbonautomat:

DEA - Deterministischer endlicher Automat

Definition

Ein Automat heißt deterministisch, wenn für jeden seiner Zustände für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt. Der deterministische endliche Automat ist genau wie der Mealy-Automat dadurch gekennzeichnet, dass er eine endliche Menge an Zuständen besitzt und die Übergänge von einem Zustand zum anderen deterministisch definiert sind, es also keine Wahlmöglichkeiten für den Zustandswechsel bei einer konkreten Eingabe gibt. Er besitzt jedoch kein Ausgabealphabet und keine Ausgabefunktion, dafür aber eine Menge an akzeptierenden Endzuständen.

Bildlich kann man sich den DEA wie eine Blackbox vorstellen, die sich einem Zustand S befindent und eine Folge von Buchstaben aus ∑ liest. Der DEA geht die Buchstaben einzeln durch bis ein Wort entsteht und gemäß Zustandsübergangsfunktion einen Folgezustand erreicht wird, der einen definierten Endzustand für den DEA darstellt.

Solche DEA können z. B. überprüfen, ob in einer Kaffeemaschine das Kaffeeersatzfach geleert werden muss. Dazu muss eine Spezifikation des Problems vorliegen, anhand derer sich das Problem als deterministischer Automat formalisieren lässt.

Formal definiert man einen DEA als 5-Tupel  A = {Q,s,∑,F, δ}:

Beispiel


Nichtdeterministischer endlicher Automat

Definition

Ein nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den Zustandsübergang mehrere gleichwertige Möglichkeiten gibt. Im Unterschied zum deterministischen endlichen Automaten sind die Möglichkeiten nicht eindeutig, dem Automaten ist also nicht vorgegeben, welchen Übergang er zu wählen hat.

Formal kann ein NEA A als (5-Tupel ( Q , Σ , Δ , S , F) definiert werden. Hierbei gilt Folgendes:

Zudem gilt das Wort W zur Sprache L des Automaten gehört. wenn W ∈ ∑ ist und zu einem Endzustand F führt.

Beispiel

Folgendes Diagramm stellt NEA und DEA gegenüber. Es wurde ein einfacher Spam-Filter als Automat entwickelt.

Potenzmengenkonstruktion

Die Potenzmengenkonstruktion ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten (NEA) in einen äquivalenten deterministischen endlichen Automaten (DEA) umwandelt.

Die Zustände des aus dem NEA abzuleitenden DEA sind Mengen von Zuständen des NEA. Ein Zustand vom DEA kodiert dabei all diejenigen Zustände, in denen sich der äquivalente nichtdeterministische Automat NEA zu einem bestimmten Zeitpunkt befinden könnte. Ein Zustandsübergang im DEA ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die ein NEA unter einer bestimmten Eingabe gelangen kann. Das Verfahren heißt Potenzmengenkonstruktion, weil die Zustände des konstruierten Automaten Mengen von Zuständen des Ausgangsautomaten sind und daher die konstruierte Zustandsmenge Teil der Potenzmenge der Zustandsmenge des Ausgangsautomaten ist. 


Wir bertachten folgenden NEA als 5-Tupel (Quelle: https://de.wikipedia.org/wiki/Potenzmengenkonstruktion#Beispiele)

Die Übergangsfunktion des NEA lässt sich durch folgenden Graph beschreiben:

Nach obiger Konstruktion ergeben sich die Zustandsmenge Q′={S0′,S1′,S2′,S3′}  und die Übertragungsfunktion δ′ des äquivalenten deterministischen Automaten wie folgt: 

Neue Finalzustände sind die Zustände, die den Finalzustand des ursprünglichen NEA enthalten. Hier also S3′, da S3′ s3 enthält. Möglich ist, dass der abgeleitete DEA mehr Finalzustände besitzt als der zugrundeliegende NEA, da alle neuen Zustandsmengen die einen alten Finalzustände enthalten nun Endzustände sind. Insgesamt ergibt sich der deterministische Automat , der folgende graphische Darstellung besitzt:

Deterministischer endlicher Automat 3.png

Quelle:https://de.wikipedia.org/wiki/Datei:Deterministischer_endlicher_Automat_3.png

ε-NEA

ε-NEAs sind ein nützliches Werkzeug in der Theorie formaler Sprachen und Automatentheorie. Sie bieten Flexibilität und können in vielen Fällen den Design- und Analyseprozess vereinfachen, da Sie es ermöglichen, Zustände ohne das Verarbeiten eines Symbols zu wechseln. Das kann in manchen Situationen die Konstruktion eines Automaten erleichtern. In manchen Fällen kann ein ε-NEA eine kompaktere und klarere Darstellung eines Problems oder einer Sprache bieten als ein NEA oder DEA.

Um die Darstellung von endlichen Automaten zu vereinfachen, können  Zustands­übergänge  ohne Einlesen eines Zeichens ausgelöst werden. Diese Zustandsübergänge bezeichnet man als Epsilon-Übergänge. Für jeden nicht­deterministischen endlichen Automaten mit Epsilon-Übergängen gibt es einen nicht­deterministischen endlichen Automaten ohne Epsilon-Übergänge, der dieselbe Sprache erkennt, und umgekehrt. Die beiden Maschinen­modelle sind also äquivalent. Genau wie der normale nicht­deterministische endliche Automat erkennt ein nicht­deterministischer endlicher Automat mit Epsilon-Übergängen ein Wort w, wenn es in seinem Zustands­graphen einen Pfad vom Startzustand zu einem Endzustand gibt.

Umwandlung ε-NEA zu NEA

Jeder ε-NEA lässt sich in einen NEA ohne ε-Übergänge umwandeln. Hierfür entfernt man die  ε-Übergänge und betrachtet die Zustandsmengen, die von den Zuständen Q inklusive ε-Übergänge erreicht werden können. Für diese resultierenden Zustandsmengen wird analog zum Verfahren der Potenzmengenkonstruktion ein NEA ohne ε-Übergänge abgeleitet.

Beispiel

Das folgende Diagramm beschreibt einen NEA mit ε-Übergängen. Er wird in der Folge in einen NEA ohne ε-Übergänge umgewandelt.

Quelle: https://hwlang.de/theor/index.htm

Dieser Automat lässt sich als 5-Tupel beschreiben:

Als erstes erfassen wir die Zustandsmengen, die von den Zuständen Q durch das Eingabealphabet erreicht werden können. Wir beginnen mit dem Startzustand. Dieser ist nun {2,0}. Denn man kann direkt ohne Eingabe von 2 auf 0 weiterziehen, da im ε-NEA ein ε-Übergang zwischen dem ursprünglichen Startzustand 2 und 0 definiert wurde. Von {0,2} kann man mit a oder ε die Zustände {1,3,4,5,6} erreichen. b führt von {2,0} nirgendwo hin. Von {1,3,4,5,6} kann man mit a oder ε {1,3,4,5,6,7} erreichen. Man kann z.B. von 4 nach 6 mit ε, von 6 nach 7 mit a und dann noch von 7 zurück nach 4 mit ε. Alles in einem Zug durch die Eingabe a!

 Epsilon-Hülle

Die Epsilon-Hülle beschreibt die Menge an Zuständen die von einem Ausgangszustand mit Hilfe eines Epsilons erreicht werden können. Dies beinhaltet auch immer den Ausgangszustand selbst. Die Epsilon-Hülle von 4 ist {4,5,6}. Merke! 4 ist als Ausgangszustand Teil der Epsilon-Hülle. Die Epsilon-Hülle von 7 ist {7,4,5}.

Potenzmengen-Reduktion vom ε-NEA

Beim DEA ist immer noch ein Zustandsübergang pro Zeichen erlaubt. Daher bilden die Mengen, in die man wechseln kann die neuen Zustände (siehe Potenzmengen Reduktion). Nun muss man noch beachten, dass gegeben Falls weitere Zustände mit dem Epsilon-Übergang erreichen werden können und diese in die Mengen aufgenommen werden werden müssen. 

Beispiel: Der Startzustand des NEA ist 2. Doch mit Epsilon erreicht man auch 0. Die Epsilon-Hülle von 2 ist also {2,0}. Somit ist de der Startzustand des DEA die Menge {2,0}.

Von der Menge {2,0} komme ich von 2 mit einem a in 4. Von 0 kann man mit a in 1 springen und mit Epsilon erreicht man dann  3. Von 4 erreicht mit dem Epsilon 5 und 6. Hieraus ergibt sich die Menge {1,3,4,5,6}. Da 3 in der Menge endhalten ist, ist diese auch gleichzeitig ein Endzustand.

Grenzen endlicher Automaten

Jeder Taschenrechner beherrscht die Klammerung von Ausdrücken, d. h. zu jeder öffnenden Klammer muss es eine schließende Klammer geben. Dabei müssen sich an jeder beliebigen Stelle der Eingabe stets rechts von der Eingabemarke mehr oder gleich viele öffnende Klammern sein wie schließende Klammern und am Eingabeende gleich viele öffnende und schließende Klammern, sonst wird die Eingabe nicht akzeptiert.

Beispiel: ((3 + 5) / 6) * (10 / ( 24 - 12) + 44) = ?

Wir wollen das Beispiel etwas vereinfachen und überlegen, ob ein Akzeptor die "Klammersprache" erkennen kann. Die Sprache soll L = {ab, aabb, aaabbb, ... } = {anbn | n > 0} sein. Diese Sprache kann als Teil der o. g. Klammersprache gesehen werden.
Für n endlich ist die Umsetzung kein Problem:

Beispiel: n ≤ 3: L=  {anbn | n > 0}

Eine Erweiterung scheint problemlos möglich, man muss nur weitere neue Zustände einführen. Im allgemeinen Fall würde der Automat aber unendlich viele Zustände besitzen müssen. Es scheint also, dass diese Sprache nicht vom Automaten erkannt werden kann.

Um die Sprache zu erkennen, ist es notwendig, dass sich der Automat irgendwie die Anzahl der n-mal gelesenen Buchstaben merkt. 

Hier für ist das Konzept des Kellerautomaten geeignet.


Modellierung

Das Zustandsdiagramm (englisch state diagram) ist eine der 14 Diagrammarten der Sprache UML für Software und andere Systeme. Es stellt einen endlichen Automaten in einer UML-Sonderform grafisch dar und wird benutzt, um entweder das Verhalten eines Systems oder die zulässige Nutzung der Schnittstelle eines Systems zu spezifizieren.