Endlicher Automat
Endliche Automaten sind mathematische Modelle von sehr einfachen Rechenmaschinen, die besonders in der theoretischen Informatik, insbesondere bei Berechenbarkeitstheorie und dem Compilerbau Anwendung finden.
Definition
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 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.
Ein Mealy-Automat ist ein endlicher Automat, der die Ausgabe in Verbindung mit den Zustandsübergängen (Transition) liefert, bei einem Moore-Automat ist mit jedem Zustand eine Ausgabe verknüpft.
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.
Endliche Automaten spielen insbesondere beim Parsen von Dokumenten eine wichtige Rolle.
Definition
Formal kann ein endlicher Automat als 5-tupel {Z,z0,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 Zustände \Sigma das Eingabealphabet und
\delta : Z \times \Sigma \rightarrow Z eine Zustandsübergangsfunktion ist
Beispiel
Dieser endliche Automat addiert zwei binäre Zahlen. Neben seinem Anfangszustand benötigt er nur einen weiteren Zustand z1, 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 => 22 = 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.