| |
|
| Table of contents |
|
2 Siehe auch 3 Weblinks |
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.
Jede durch einen endlichen Automaten erkennbare Sprache ist regulär (vgl. Chomsky-Hierarchie).
Bei deterministischen endlichen Automaten gibt es für diesen Zustandsübergang nur eine Möglichkeit, bei nichtdeterministischen endlichen Automaten sind mehrere Übergänge möglich.
Welche Möglichkeiten es gibt, hängt vom speziellen Automaten, also 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: