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.Endliche Automaten spielen insbesondere beim Parsen von Dokumenten eine wichtige Rolle.
Table of contents |
2 Typen 3 Formale Definition 4 Werkzeuge 5 Siehe auch 6 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).
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.
Man kann also die Gültigkeit eines Eingabewortes überprüfen, d.h. überprüfen, ob ein gegebenes Wort in einer Sprache ist oder nicht.
Erreicht wird dies durch den Automaten, indem er im Startzustand beginnt die einzelnen Buchstaben des Wortes einzulesen und bei jedem Buchstaben den Zustand wechselt (er kann auch im Zustand verbleiben). Ist das Ende des Wortes erreicht, entscheidet die Gültigkeit des Wortes am letzten Zustand. Ist der Zustand in der Menge (s.u) wird das Wort akzeptiert und gehört somit zur entsprechenden Sprache, andernfalls ist das Wort ungültig.
Eine weitere Variante sind die sogenannten ω-Automaten, bei denen die Eingabe eine unendliche Folge von Symbolen ist. Bei diesem Automatenmodell wird die Akzeptanz üblicherweise durch die Menge der Zustände beschrieben, die unendlich oft angenommen werden. Der griechische Buchstabe ω (omega) steht hier für die kleinste unendliche Ordinalzahl.
Weiterhin lassen sich die endlichen Automaten in drei Gruppen aufteilen:
Typen
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.Werkzeuge
Siehe auch
Weblinks