Zum Inhalt springen

Endlicher Automat

Aus FLBK-Wiki

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 an Ein- und Ausgaben. Das durch den Automaten beschriebene System befindet sich in einem von endlich vielen Zuständen. Das Verhalten des Systems wird durch Zustände, Zustandsübergänge und Aktionen beschrieben.

Automaten lassen sich unter anderem durch ein UML Zustandsdiagramm darstellen.

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 π berechnen, einem sagen, was man als Nächstes kaufen möchte, oder wenn 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 seine 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 neuronale Netze darauf zurück. Automaten findet man außerdem in zahlreichen Alltagssituationen vor: Fahrstühle, Ampeln, 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.

Mealy-Automat

Hauptartikel: Mealy-Automat

Definition

Ein Mealy-Automat ist ein endlicher Automat mit Ausgabe: Zu jedem gelesenen Zeichen des Eingabealphabets gibt er ein Zeichen des Ausgabealphabets aus. Die Übergangsfunktion legt den Folgezustand fest, die Ausgabefunktion die Ausgabe; beide werden tabellarisch oder als Übergangsgraph dargestellt.

Formal definiert man einen Mealy-Automaten als 7-Tupel [math]\displaystyle{ A = (Q, \Sigma, \Omega, \delta, \lambda, q0, F) }[/math]:

[math]\displaystyle{ Q }[/math] ist eine nicht leere, endliche Menge von Zuständen

[math]\displaystyle{ \Sigma }[/math] ist ein nicht leeres, endliches Eingabealphabet

[math]\displaystyle{ \Omega }[/math] ist ein nicht leeres, endliches Ausgabealphabet

[math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math] ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.

[math]\displaystyle{ \lambda: Q \times \Sigma \to \Omega }[/math] ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Ausgabe zuordnet.

[math]\displaystyle{ q0 \in Q }[/math] ist der Startzustand

[math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der Endzustände. Oft ist jeder Zustand ein Endzustand, also [math]\displaystyle{ F = Q }[/math]. In der Literatur ist auch das 6-Tupel ohne [math]\displaystyle{ F }[/math] üblich.

Beispiel

Die Funktionsweise eines endlichen Automaten lässt sich leicht an einer einfachen Maschine wie einem Bonbonautomaten erläutern. Die Eingabe besteht aus der richtigen Münze (M) und dem Drehen des Hebels (H). Die Verarbeitung erfolgt im Inneren des Automaten und führt zur Ausgabe, dem Bonbon (B) im Ausgabefach oder keiner Ausgabe (N). Es kommt 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.

Bonbonautomat als Mealy-Automat: [math]\displaystyle{ Q = \{q0, q1\} }[/math], [math]\displaystyle{ \Sigma = \{M, H\} }[/math], [math]\displaystyle{ \Omega = \{B, N\} }[/math], [math]\displaystyle{ F = Q }[/math]

Bonbonautomat als Mealy-Automat

Übergangsfunktion

Die Übergangsfunktion [math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math] 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

Endzustände werden in der Tabelle mit einem Stern gekennzeichnet.

Beispiel Übergangsfunktion für den Bonbonautomaten:

δ M H
q0 q1 q0
q1 q1 q0

DEA - Deterministischer endlicher Automat

Hauptartikel: Deterministischer endlicher Automat

Definition

Ein Automat heißt deterministisch, wenn für jeden seiner Zustände für jedes Eingabezeichen 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.

Solche DEA können z. B. überprüfen, ob in einer Kaffeemaschine das Kaffeesatzfach 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 [math]\displaystyle{ A = (Q, \Sigma, \delta, q0, F) }[/math]:

[math]\displaystyle{ Q }[/math] ist eine nicht leere, endliche Menge von Zuständen

[math]\displaystyle{ \Sigma }[/math] ist ein nicht leeres, endliches Eingabealphabet

[math]\displaystyle{ \delta: Q \times \Sigma \to Q }[/math] ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen einen Nachfolgezustand zuordnet.

[math]\displaystyle{ q0 \in Q }[/math] ist der Startzustand

[math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der zu akzeptierenden Endzustände

Vollständiger DEA des Kaffeeautomaten

Nichtdeterministischer endlicher Automat

Hauptartikel: 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 als 5-Tupel [math]\displaystyle{ A = (Q, \Sigma, \delta, q0, F) }[/math] definiert werden. Hierbei gilt Folgendes:

[math]\displaystyle{ Q }[/math] ist eine nicht leere, endliche Menge von Zuständen

[math]\displaystyle{ \Sigma }[/math] ist ein nicht leeres, endliches Eingabealphabet

[math]\displaystyle{ \delta: Q \times \Sigma \to P(Q) }[/math] ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Eingabezeichen eine Menge von Folgezuständen zuordnet. [math]\displaystyle{ P(Q) }[/math] ist die Potenzmenge von [math]\displaystyle{ Q }[/math].

[math]\displaystyle{ q0 \in Q }[/math] ist der Startzustand

[math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der zu akzeptierenden Endzustände

Ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] gehört zur Sprache des Automaten, wenn mindestens ein Pfad nach dem Lesen von [math]\displaystyle{ w }[/math] in einem Endzustand endet.

Beispiel

Spam-Filter als NEA
Spam-Filter als DEA

Folgende Diagramme stellen NEA und DEA gegenüber. Es wurde ein einfacher Spam-Filter als Automat entwickelt, der E-Mails mit der Zeichenfolge UML erkennt.


Potenzmengenkonstruktion

Hauptartikel: 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 des 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.

ε-NEA

Hauptartikel: Nichtdeterministischer endlicher Automat#ε-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 nichtdeterministischen endlichen Automaten mit Epsilon-Übergängen gibt es einen nichtdeterministischen endlichen Automaten ohne Epsilon-Übergänge, der dieselbe Sprache erkennt, und umgekehrt. Die beiden Maschinenmodelle sind also äquivalent. Genau wie der normale nichtdeterministische endliche Automat erkennt ein nichtdeterministischer endlicher Automat mit Epsilon-Übergängen ein Wort w, wenn es in seinem Zustandsgraphen einen Pfad vom Startzustand zu einem Endzustand gibt, der genau die Zeichen von w liest.

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 aus Q über ε-Übergänge erreicht werden können. Für diese resultierenden Zustandsmengen wird analog zum Verfahren der Potenzmengenkonstruktion ein NEA ohne ε-Übergänge abgeleitet.

Beispiel

ε-NEA

Das Diagramm zeigt einen ε-NEA, der Wörter akzeptiert, die nur aus a oder nur aus b bestehen, auch das leere Wort. Von q0 führen ε-Übergänge nach q1 und q2, die beide Endzustände sind.

Die Umwandlung in einen DEA zeigt Potenzmengenkonstruktion#ε-NEA in einen DEA überführen.