Morgen ist meine Präsentation und ich möchte meine Konzepte klären ...
Ich habe gelesen, dass in DFA "Für jeden Zustand sollte der Übergang für alle möglichen Symbole (Alphabet) definiert werden."
Ist für jeden Status die Definition des Übergangs für alle möglichen Symbole in DFA obligatorisch? Wenn nicht, geben Sie bitte Beispiele an.
Antworten:
Ein DFA wird durch die folgenden Daten angegeben:
Wie Sie an der Signatur von , gibt es für jedes Symbol einen Übergang in jedem Zustand an.δ
quelle
Angenommen, ein DFA darf fehlende Übergänge aufweisen. Was passiert, wenn Sie auf ein Symbol stoßen, für das keine Transtion definiert ist? Das Ergebnis ist undefiniert. Dies scheint das "deterministische" Merkmal eines DFA zu verletzen.
Es ist jedoch trivial, einen solchen unvollständigen DFA in einen vollständigen DFA umzuwandeln . Fügen Sie einfach einen neuen Status hinzu
illegal
und ordnen Sie alle nicht definierten Übergänge demillegal
Status zu. Fügen Sie schließlich für jedes Symbol Übergänge vomillegal
Status zurück zu sich selbst hinzu. Dieserillegal
Zustand wird oft als Senkenzustand bezeichnet , da es keine Möglichkeit gibt, herauszukommen, sobald Daten in die Senke gelangen.Aus praktischer Sicht ist es also eine Art Streit, solange Sie einen genau definierten Weg haben, um mit fehlenden Übergängen umzugehen.
quelle
Ein Wort wird von einer NFA akzeptiert, wenn es einen akzeptierenden Lauf hat. Ein deterministischer Automat hat höchstens einen Lauf. Ein vollständiger Automat hat mindestens einen Lauf.
Einige Autoren definieren trim Automaten als solche , in denen jeder Zustand auf irgendeinem Pfad von einem Anfangszustand zu einem Endzustand ist. Für bestimmte Sprachen können keine beschnittenen und vollständigen Automaten vorhanden sein. In diesen Fällen ist es zweckmäßig, die Vollständigkeitsanforderung aus der Definition des deterministischen Automaten herauszuhalten.
quelle