Übersicht Automaten
3. Endliche Automaten
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 Anfangszustand.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.
Akzeptieren der Reguläre Sprachen
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.
Man kann also die Gültigkeit eines Eingabewortes überprüfen, d.h. überprüfen, ob ein gegebenes Wort in einer Sprache ist oder nicht.