Potenzmengenkonstruktion
Mittels der Potenzmengenkonstruktion können wir in der theoretischen Informatik einen NEA in einen DEA umwandeln. Wie das funktioniert, erklären wir dir in diesem Beitrag und Video anhand eines Beispiels.
Die Potenzmengenkonstruktion ist ein Verfahren, mit dem ein nichtdeterministischer endlicher Automat in einen äquivalenten, deterministischen endlichen Automaten umgewandelt werden kann. Dieses Verfahren wird manchmal auch Myphill-Konstruktion oder Teilmengenkonstruktion genannt.
Inhaltsübersicht
Unterschied deterministischer – nichtdeterministischer Automat
Zu Beginn eine kurze Wiederholung: ein DEA hat genau einen Startzustand, immer eindeutig definierte Zustandsübergänge und ist meist größer beziehungsweise aufwendiger als der NEA.
Der nichtdeterministische endliche Automat hingegen hat eine Menge aus Startzuständen und kann deshalb also an mehr als einem Zustand beginnen. Außerdem ist bei Zustandsübergängen oft nicht eindeutig, welchen der Automat benutzen soll, weil es, anders als beim DEA, mehrere Möglichkeiten geben kann.
In diesem Video kannst du dir noch einmal alles Wichtige zum nichtdeterministischen Automat anschauen.
NEA zu DEA – Potenzmengenkonstruktion
Man kann aus jedem beliebigen NEA einen DEA erstellen. Hierfür benötigen wir die Potenzmengenkonstruktion. Und genau die schauen wir uns jetzt einmal näher an.
Potenzmenge
Stell dir die folgende Menge M = { A , B , C } vor.
Die dazugehörige Potenzmenge P(M) = { {A, B, C}, {A, B}, {A, C}, {B, C}, {A}, {B}, {C}, {∅} } ist nun jede Teilmenge, die sich aus M ableiten lässt.
Hierbei gilt, dass die Potenzmenge von k Elementen danach 2k Elemente enthält. Achtung! Die leere Menge ist Teil jeder Menge und muss stets enthalten sein!
Wie du hier sehen kannst, ergeben sich für die Menge M mit 3 Elementen als Potenzmenge 23 also 8 Elemente.
Teilmengenkonstruktion – Beispiel
Um die Zustände des DEA aus einem NEA zu erhalten, erstellt man nun die Potenzmenge der Zustände des NEA. Die Zustandsübergänge sind hierbei jeweils die kombinierten Zeilen des aktuellen Zustands. Klingt ganz schön kompliziert. Darum schauen wir uns das jetzt an einem konkreten Beispiel an.
Dafür wollen wir diesen NEA in einen DEA umwandeln:
Um welche Art von Automaten handelt es sich? Man sieht, dass es bei Zustand z0 für die Eingabe b mehrere mögliche Zustandsübergänge gibt. Somit können wir feststellen, dass es sich um einen NEA handelt.
Zustandsmenge
Jetzt kann es losgehen. Wir bilden wie vorhin erklärt die Potenzmenge der Zustände. Um das Ganze möglichst übersichtlich zu halten, nennen wir entstehende Teilmengen wie die Menge {z0, z1, z2} einfach z012. Unsere neuen Zustände sehen also so aus:
Z‘ = { {z012}, {z01}, { z02}, { z12}, {z0}, {z1}, {z2}, {∅}}
Nun können wir die Zustandsübergangstabelle des DEA, in den wir den NEA umwandeln wollen, erstellen. Die Zustände können wir dann einfach eintragen. Doch was schreiben wir jetzt in die Übergänge?
Ganz einfach: z012 kombinieren wir alle Übergänge bei Eingabe a . Wir kombinieren diese zu z02 und schreiben sie in die neue Tabelle als Folgezustand von z012. Diesen Vorgang wiederholen wir nach und nach für jede Zelle.
Finalzustände
Am Ende erhalten wir die folgende Tabelle:
Alle Zustände, die hierbei den ehemaligen Endzustand – also z2 – enthalten, werden zu Endzuständen.
Dieser Potenzautomat sieht als Zustandsübergangsdiagramm so aus:
Es fällt direkt auf, dass ein großer Teil des Automaten überhaupt nicht mit dem anderen Teil verbunden ist. Da es keinen Weg vom Startzustand zum nicht verbundenen Teil gibt, gilt dieser als unerreichbar und hat somit keine Auswirkung auf den Ablauf des Automaten. Er kann einfach entfernt werden.
Wenn du genauer wissen willst, warum ein Teil des Automaten entfernt werden konnte oder wie du noch weiter minimieren kannst, schau dir unsere Videos endliche Automaten und DEA minimieren an.
Sehr gut! Nun weißt du, wie du mit dem immer gleichbleibenden Schema der Potenzmengenkonstruktion einen nichtdeterministischen endlichen Automaten in einen deterministischen umwandeln kannst. Damit steht deinem Potenzautomaten nichts mehr im Weg!