Potenzmengenkonstruktion Bedeutung, Erklärung und Definition.
Die Potenzmengenkonstruktion ist ein Verfahren, das einen nichtdeterministischen endlichen Automaten NEA in einen äquivalenten deterministischen endlichen Automaten DEA umwandelt. Das Verfahren dient als konstruktiver Beweis für die Äquivalenz der beiden Automatenmodelle.
| Table of contents |
|
2 Konstruktion 3 Formal 4 Beispiele |
Die Zustände des konstruierten deterministischen Automaten DEA sind Mengen von Zuständen des nichtdeterministischen Automaten NEA. Ein Zustand von DEA kodiert dabei all diejenigen Zustände, in denen sich der äquivalente nichtdeterministische Automat NEA zu einem bestimmten Zeitpunkt befinden könnte. Ein Zustandsübergang in DEA ist deterministisch, da sein Folgezustand aus der Menge aller möglichen Folgezustände besteht, in die NEA unter einer bestimmten Eingabe gelangen kann.
Das Verfahren heißt Potenzmengenkonstruktion, weil die Zustände des konstruierten Automaten Mengen von Zuständen des Ausgangsautomaten sind und daher die konstruierte Zustandsmenge Teil der Potenzmenge der Zustandsmenge des Ausgangsautomaten ist.
Zu einem nichtdeterministischen Automaten konstruiere einen äquivalenten deterministischen Automaten folgendermaßen:
Grundidee
Konstruktion
Formal
In der Regel sind viele der Zustände des neuen Automaten nicht erreichbar und können in einem weiteren Vereinfachungsschritt weggelassen werden. In der Praxis würde man eine Variante der Konstruktion benutzen, bei der nur der erreichbare Teil des Automaten erzeugt wird. Es gibt Beispiele, die zeigen, dass sich das exponentielle Anwachsen der Zustandsanzahl (die Potenzmenge einer Menge mit Elementen hat Elemente) nicht immer vermeiden läßt.
| a | b | |
Eine graphische Darstellung des Ausgangsautomaten sieht folgendermaßen aus:
Nach obiger Konstruktion ergeben sich die Zustandsmenge und die Übertragungsfunktion des äquivalenten deterministischen Automat wie folgt:
| a | b | |
Daraus leitet sich die Menge der Finalzustände ab, da nur den Finalzustand des Ausgangsautomaten enthält. Insgesamt ergibt sich der deterministische Automat , der folgende graphische Darstellung besitzt:
Automat zum regulären Ausdruck a(a|b)*b
| NEA mit dem Regex a(a|b)*b |
| a | b | |
| S'0 = S0 | S1 | 0 |
| S'1 = S1 | S1 | {S1,S2} |
| S'2 = {S1,S2} | S1 | {S1,S2} |
| 0 | 0 | 0 |
| DEA mit dem Regex a(a|b)*b |
Diese Seite ist ein Artikel über Potenzmengenkonstruktion. Seite Versuche, zum von von Beschreibung über bereitzustellen Potenzmengenkonstruktion. Sie konnten Tatsachen über auch finden Potenzmengenkonstruktion. Erklärung von Potenzmengenkonstruktion.