Endlicher Automat

Endliche Automaten (Abk. EA, engl. finite automaton - FA oder finite state Machine - FSM) sind mathematische Modelle von einfachen idealen Rechenmaschinen. Die Automatentheorie ist ein Teilgebiet der theoretischen Informatik, mit Bezug zur Theorie der formalen Sprachen. Sie hat viele Anwendungen, u.a. im Compilerbau, Model Checking, Modellierung von Parallelen Prozessen, Beschreibung von digitalen Schaltwerken. Endlich heißt der Automat deshalb, weil die Anzahl seiner inneren Zustände endlich ist und er letztlich nur Wörter endlicher Länge akzeptieren kann.

Endliche Automaten können genau die Wörter der sog. regulären Sprachen erkennen. Daher werden sie zur Worterkennung genutzt, insbesondere zur Erkennung von Wortmengen, die durch reguläre Ausdrücke spezifiziert sind.

Im Zusammenhang mit dem Parsen von Dokumenten setzt man endliche Automaten zur Tokenerkennung ein, um den Zeichenstrom zu einem Tokenstrom zu kondensieren, auf dem dann das Parsen stattfindet.

Einführung

Ein endlicher Automat liest eine endliche Folge von Symbolen, das Eingabewort, aus einer endlichen Menge von Symbolen, dem Eingabealphabet und gibt an, ob er dieses Wort akzeptiert oder nicht, indem er hält oder nicht.

Ein endlicher Automat mit Ausgabe (Moore- oder Mealy-Automat) schreibt dabei auch gemäß seiner Programmierung eine endliche Folge von Symbolen, das Ausgabewort, aus einer Menge von Symbolen, dem Ausgabealphabet.

Ein endlicher Automat lässt sich als endliches Transitionssystem beschreiben.

Je nach Programm, das der Automat implementiert, besitzt er eine kleinere oder größere endliche Anzahl von Zuständen, in denen er sich befinden kann. Zu Beginn befindet er sich in einem speziell ausgezeichneten Startzustand.

Beim Lesen der Eingabe und Schreiben der Ausgabe geht der Automat schrittweise vor, wobei er in jedem Schritt das jeweils nächste Symbol des Eingabewortes liest. Abhängig von diesem Eingabesymbol und dem momentanen Zustand produziert er dann in einem Bearbeitungsschritt eine endliche Folge von Ausgabesymbolen (und erweitert so die Ausgabe) und geht in einen neuen Zustand über.

Neben diesem sog. endlichen Einweg-Automat (1EA), der die Eingabe monton von links nach rechts liest, kann man auch einen sog. endlichen Zweiweg-Automat (2EA) definieren, der nach dem Lesen des Symbols den Kopf nach links oder rechts bewegen kann. Allerdings führt diese erhöhte Freiheit in der Kopfbewegung nicht zu einer Erhöhung der Erkennungsleistung. 1EA und 2EA erkennen genau die regulären Sprachen.

Grenzen der Spracherkennung

Die Sprachen, die endliche Automaten akzeptieren sind genau die regulären Sprachen. Es gibt z.B. keinen endlichen Automaten, der die Sprache

L=a^{*}b^{*}=\{a^{n}b^{n}|n\in \mathbb {N} \}

,

also $\varepsilon$ , ab, aabb, aaabbb, aaaabbbb etc. und sonst nichts akzeptiert.

In der Praxis machen sich diese Einschränkungen am häufigsten dadurch bemerkbar, dass mit endlichen Automaten nicht überprüft werden kann, ob etwa Formeln korrekt geklammert sind. Dafür reicht ein endlicher Speicher nicht aus. Ein Automat mit n verschiedenen Zuständen könnte sich allerhöchstens n Klammerebenen merken und würde dann an einem Ausdruck mit mehr Klammerebenen scheitern. Ein Automat, der solche wohlgeformten Klammerausdrücke beliebiger Tiefe akzeptieren kann, braucht daher ein potentiell unendlich grosses "Gedächtnis", wie beispielsweise ein Kellerautomat. Auch eine Turing-Maschine ist dazu in der Lage.

Darstellung

Ein endlicher Automat lässt sich vollständig graphisch darstellen:


Zustandsdiagramm

Das Diagramm liest sich wie folgt:

Kreise stellen Zustände dar.
Im Kreis steht der Name des Zustands bzw. der Zustand.
Der Anfangszustand ist dadurch gekennzeichnet, dass er Endpunkt eines Pfeils ist, der keinen Zustand als Ausgangspunkt hat.
Pfeile zwischen Zuständen stellen die Transitionen dar. Auf den Pfeilen steht, welches Zeichen (oder gar welches Wort) der Automat bei der Transition liest.
Endzustände sind durch doppelte Kreise gekennzeichnet.

Die Transitionsfunktion des obigen deterministischen Automaten lässt sich auch als Zustandstabelle darstellen:

	a	b
S0	S0	S1
S1	S0	S2
S2	S1	S2

Zustandstabelle

Typen

Deterministische endliche Automaten haben bei jedem Zustand für jedes Symbol ihres Alphabets genau eine Transition.

Bei nichtdeterministischen endlichen Automaten sind für ein gelesenes Symbol mehrere Übergänge oder gar kein Übergang möglich. Beispiel für einen NEA

Man kann zudem noch $\varepsilon$ -Transistionen zulassen, womit Zustandsänderungen möglich sind, ohne das ein Symbol gelesen wird.

Eine weitere Variante sind die so genannten ω-Automaten, bei denen die Eingabe eine unendliche Folge von Symbolen ist. Bei diesem Automatenmodell wird die Akzeptanz üblicherweise durch die Menge der Zustände beschrieben, die unendlich oft angenommen werden.

Weiterhin lassen sich die endlichen Automaten mit Ausgabe in drei Gruppen aufteilen:

Mealy-Automat: Die Ausgabe hängt von der Eingabe und vom Zustand des Automaten ab.
Moore-Automat: Die Ausgabe hängt nur vom Zustand ab.
Medwedjew-Automat: Ausgabe und Zustand sind identisch.

Fügt man dem endlichen Automaten noch Variablen mit endlichem Wertebereich hinzu, welche dann als Vorbedingung zur Ausführung von Transitionen herangezogen oder bei einer Transition gesetzt werden können, so erhält man einen erweiterten endlichen Automaten (EFSM). Aufbauend auf EFSMs wurde z.B. die Systembeschreibungssprache SDL entwickelt. Ebenso lassen sich Kommunikationsprotokolle, wie z.B. das Netzwerkprotokoll HDLC durch geeignete Automaten darstellen. Dort gibt es z.B. Transitionen, die der Automat nach Ablauf eines Timers vollzieht.

Formale Definition

Ein deterministischer endlicher Automat (DEA) ist ein 5-Tupel:

M=\left(Q,\Sigma ,\delta ,q_{0},F\right)

Dabei sind die Elemente des Tupels wie folgt definiert:

$Q$ ist eine endliche Menge, deren Elemente man als Zustände bezeichnet.

$\Sigma$ ist eine endliche Menge, die man als Alphabet bezeichnet. Ihre Elemente bezeichnet man als Symbole.

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle \delta : \Sigma \times Q \to Q} ist die Transitionsfunktion.

$q_{0}\in Q$ ist der Anfangszustand.

$F\subseteq Q$ ist die Menge der Endzustände.

Ein nichtdeterministischer endlicher Automat (NEA) ist ein 5-Tupel:

M=\left(Q,\Sigma ,\Delta ,q_{0},F\right)

Dabei besitzt der NEA eine

Transitionsrelation $\Delta \subseteq Q\times \Sigma \times Q$ ,

anstelle der Transitionsfunktion $\delta$ des DEA.

Werkzeuge

AT&T FSM Library ™ [1]
AutoFSM [2]
Bandera [3]
Covered [4]
Dynamic Attachment Finite State Machine (DAFSM) [5]
Exorciser [6]
Finite State Kernel Creator [7]
Finite State Machine Editor [8]

Finite State Machine Explorer [9]
FSMGenerator [10]
FSA Utilities [11]
JFLAP [12]
jrexx-Lab [13]
Kara [14]
Nunni FSM Generator [15]
Petrify [16]

Qfsm [17]
Quantum-Leaps [18]
Ragel [19]
Statestep [20]
StateWORKS [21]
WhatOS [22]
Xerox Finite-State Software Tools [23]

Endliche Automaten zeichnen

Es gibt auch Softwarewerkzeuge, um die Graphen endlicher Automaten in ansprechender Form zu generieren. Beispielsweise kann man die Xy-pic oder GasTeX Pakete für LaTeX verwenden.

% Benötigt: Paket xy mit Option curve und Paket xypic.
%
% Mein erster xymatrix-Automat!
\xymatrix{ 
{\ar[r]} &                         % Start: \ar[r] Pfeil nach r (rechts)
0 \ar[r]^a \ar@(ul,ur)[]^b &       % \ar@(ul,ur)[] Pfeil nach sich selbst
1 \ar[r]^b \ar@(ul,ur)[]^a & 
*++[o][F=]{2} \ar@(ul,ur)[]^{a,b}  % *++ grösser, [o] rund, [F=] Doppelrahmen  
}

Siehe auch

Literatur

Hopcroft, John E. und Ullman, Jeffrey D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, ISBN 3-89319-181-X
Sander, Stucky und Herschel: Automaten, Sprachen, Berechenbarkeit, ISBN 3-519-02937-5

Weblinks

Skript "Datenverarbeitende Systeme - Allgemeine Informationen" von Helmut Knebl
Vorlesungsskript "Automaten und Formale Sprachen" von Siegmar Gerber
Beschreibung aus der Wissensdatenbank eines Kompetenzzentrums
Informatikmaterialien "Formale Sprachen und Abstrakte Automaten" von Tino Hempel
Programm für die Simulation eines endlichen Automates
Gastex-Homepage