Totaler Automat
Kapitoly: Endlicher Automat, Totaler Automat, Nichtdeterministischer endlicher Automat, NKA-Simulation, Umrechnung von NKA in DKA
In der grundlegenden Definition eines endlichen Automaten ist es nicht notwendig, dass es einen Übergang von allen Zuständen zu allen Symbolen gibt. Ein totaler Automat ist ein Automat, der für alle Symbole des Eingabealphabets definierte Übergänge von allen Zuständen hat.
So konstruiert man einen totalen Automaten
Betrachten wir diesen Automaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$:
Hier ist der Übergang vom Zustand q0 für den Buchstaben "b" nicht gezeichnet. In einem solchen Fall würden wir sagen, dass der Automat das Eingabewort nicht akzeptiert. Aus Sicht der Formalisierung kann es jedoch nicht sinnvoll sein, dass die Übergangsfunktion δ für einige Werte nicht definiert ist; hier ist sie zum Beispiel für δ(q0, b) nicht definiert.
Dies kann leicht gelöst werden, indem man einen äquivalenten Automaten konstruiert, der einen zusätzlichen Zustand hat - die "fehlenden" Übergänge werden zu diesem Zustand geleitet, dieser Zustand ist nicht terminal, und alle anderen Eingaben werden bereits in diesem Zustand zirkulieren. Wir nennen diesen Automaten einen totalen Automaten. Ein modifizierter äquivalenter Automat könnte wie folgt aussehen:
Wir haben den Zustand $q_{\mbox{fail}}$ hinzugefügt. Wir haben einen Übergang von anderen Zuständen zu ihm geführt, nur für den Fall, dass der Übergang dort vorher nicht existiert hat. Dieser Zustand ist nicht-terminal und zyklisch für alle anderen Eingaben. Wenn wir also im vorherigen Automaten auf einen fehlenden Übergang gestoßen sind, gibt es hier keinen fehlenden Übergang und der Automat würde in den Zustand $q_{\mbox{fail}}$ gehen.
Wir können also ohne Verlust der Allgemeingültigkeit immer davon ausgehen, dass der Automat für alle Kombinationen von Zuständen und Buchstaben definierte Übergänge hat.
Definition von
Für den Gesamtautomaten $A=\left<Q, \Sigma, \delta, q_0, F\right>$ gilt also Folgendes
$$ \forall q \in Q\quad \forall a \in \Sigma\quad \exists r \in Q:\quad \delta(q, a) = r. $$