Endlicher Automat

Endliche Automaten sind mathematische Modelle von sehr einfachen Rechenmaschinen, die besonders in der theoretischen Informatik, insbesondere bei der Berechenbarkeitstheorie und dem Compilerbau Anwendung finden.

Beschreibung

Ein endlicher Automat liest eine endliche Folge von Symbolen, das Eingabewort, aus einer endlichen Menge von Symbolen, dem Eingabealphabet, und schreibt gemäß seiner Programmierung eine endliche Folge von Symbolen, das Ausgabewort, aus einer Menge von Symbolen, dem Ausgabealphabet.

Abhängig von seinem Programm besitzt der Automat eine bestimmte 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 des momentanen Zustandes produziert er dann in einem Bearbeitungsschritt eine endliche Folge von Ausgabesymbolen (und erweitert so die Ausgabe) und geht in einen neuen Zustand über. Bei so genannten deterministischen Automaten (auch genannt DFA - deterministic finite automaton) gibt es für diesen Zustandsübergang (Transition) nur eine Möglichkeit, bei nichtdeterministischen Automaten (auch genannt NFA - nondeterministic finite automaton) sind mehrere Übergänge möglich. Welche Möglichkeiten es gibt, hängt vom speziellen Automat, d.h. von seiner Programmierung ab.

Eine einfachere Variante, die man auch häufig als (endlicher) Akzeptor bezeichnet, produziert dagegen keine Ausgabe, sondern stoppt nach dem vollständigen Lesen der Eingabe entweder in einem akzeptierenden oder einem nichtakzeptierenden Zustand.

Weiterhin lassen sich die endlichen Automaten in zwei Gruppen aufteilen:

• Mealy-Automat
• Moore-Automat

Definition

Deterministischer endlicher Automat

Formal kann ein endlicher Automat als 5-tupel {Z,z₀,A,Σ,δ} definiert werden wobei:

• $Z$ eine endliche Menge von Zuständen
• $z_{0}\in Z$ der Startzustand
• $A\subseteq Z$ eine (endliche) Menge möglicher akzeptierender Zustände (=Endzustände, der Automat hält an, wenn er einen akzeptierenden Zustand erreicht)
• $\Sigma$ das Eingabealphabet
• und einer Übergangsfunktion $\delta :Z\times \Sigma \rightarrow Z$, $\delta (z,w)=z^{\prime }$ mit $z,z^{\prime }\in Z,w\in \Sigma$, welche jedem Zustand $z$ mit einem Eingabesymbol $w$ einen neuen Zustand $z^{\prime }$zuordnet. Weniger formal "kommt" man von $z$ nach $z^{\prime }$, wenn man in $z$ ein $w$ eingibt.

Beispiel

Zustandsdiagramm eines endlichem Automaten

Zustandsdiagramm eines endlichem Automaten

Dieser deterministische endliche Automat addiert zwei binäre Zahlen. Neben seinem Anfangszustand benötigt er nur einen weiteren Zustand z₁, der "Übertrag" entspricht. Er liest zwei Binärzahlen von rechts nach links in Paaren (x,y), die das Eingabealphabet (also alle Variationen mit Wiederholung der Menge {0,1} der Länge 2 => 2² = 4) darstellen. Die 8 Übergänge sind als Pfeile dargestellt, jeder Übergang ist von einer Ausgabe a begleitet (x,y):a - es handelt sich also um einen Mealy-Automaten.

Verwendungszwecke

Endliche Automaten spielen insbesondere beim Parsen von Dokumenten eine wichtige Rolle.

Weblinks

• qfsm ist ein (GPL) graphischer Editor für endliche Automaten