Vollständiger Automat
In der Grundfassung der Definition des endlichen Automaten ist es nicht nötig, dass aus allen Zuständen ein Übergang für alle Symbole existiert. Ein vollständiger Automat ist ein Automat, der aus allen Zuständen Übergänge für alle Symbole des Eingabealphabets definiert hat.
Wie man einen vollständigen Automaten konstruiert
Gegeben sei dieser Automat A = ⟨Q, Σ, δ, q0, F⟩:
Hier ist kein Übergang aus dem Zustand q0 für den Buchstaben „b“ eingezeichnet. Tritt eine solche Situation ein, sagen wir, dass der Automat das gegebene Eingabewort nicht akzeptiert. Aus Sicht der Formalisierung ist es jedoch nicht unbedingt günstig, wenn die Übergangsfunktion δ für manche Werte nicht definiert ist; hier ist sie zum Beispiel für δ(q0, b) nicht definiert.
Das lässt sich leicht lösen, indem wir einen äquivalenten Automaten konstruieren, der einen Zustand mehr hat – auf diesen Zustand zeigen die „fehlenden“ Übergänge, dieser Zustand ist kein Endzustand und alle weiteren Eingaben bleiben in diesem Zustand in einer Schleife. Diesen Automaten nennen wir einen vollständigen Automaten. Der geänderte äquivalente Automat könnte so aussehen:
Wir haben den Zustand qfail hinzugefügt. Aus den übrigen Zuständen haben wir genau dann einen Übergang in ihn geführt, wenn dort vorher kein Übergang existierte. Dieser Zustand ist kein Endzustand und läuft bei allen weiteren Eingaben in einer Schleife. Sind wir im vorherigen Automaten also auf einen fehlenden Übergang gestoßen, gibt es hier keinen fehlenden Übergang und der Automat würde in den Zustand qfail gelangen.
Wir können also immer ohne Beschränkung der Allgemeinheit annehmen, dass der Automat Übergänge für alle Kombinationen von Zuständen und Zeichen des Alphabets definiert hat.
Definition
Für einen vollständigen Automaten A = ⟨Q, Σ, δ, q0, F⟩ gilt also
Quellen
Kapitel: Endlicher Automat, Vollständiger Automat, Nichtdeterministischer endlicher Automat, Simulation eines nichtdeterministischen Automaten, Umwandlung eines NEA in einen DEA
