Ein endlicher Automat ist ein mathematisches Modell einer Maschine, welche eine endliche Folge von Symbolen, dem sogenannten Eingabewort, aus einer endlichen Menge E von Symbolen, dem sogenannten Eingabealphabet liest und gemäß seiner Programmierung eine endliche Folge von Symbolen, das sogenannte Ausgabewort aus einer endlichen Menge A von Symbolen, dem sogenannten Ausgabealphabet schreibt.
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 ließt. 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 sogenannten deterministischen Automaten gibt es für diesen Zustandsübergang nur eine Möglichkeit, bei nichtdeterministischen Automaten sind mehere Ü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 jeden 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 akzeptieren oder einem nichtakzeptierenden Zustand.
Endliche Automaten spielen insbesondere beim Parsen von Dokumenten eine wichtige Rolle.
Definition
Formal kann ein endlicher Automat wie folgt definiert werden...
Beipiel
Addition zweier binärer Zahlen wäre sicher hübsch?