Theoretische Informatik

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 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.

Potenzmengenkonstruktion, Unterschied deterministischer nichtdeterministischer Automat, NEA DEA
direkt ins Video springen
Unterschied deterministischer – nichtdeterministischer Automat

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.

Teilmenge
direkt ins Video springen
Potenzmengenkonstruktion

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:

Beispiel Potenzmengenkonstruktion
direkt ins Video springen
Teilmengenkonstruktion – Beispiel

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}, {∅}}

Zustandsübergänge kombinieren
direkt ins Video springen
Zustandsmenge

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:

Zustandsübergänge kombinieren
direkt ins Video springen
Zustandsübergangstabelle

Alle Zustände, die hierbei den ehemaligen Endzustand – also z2 – enthalten, werden zu Endzuständen.

Dieser Potenzautomat sieht als Zustandsübergangsdiagramm so aus:

Potenzautomat Zustandsübergangsdiagramm
direkt ins Video springen
Zustandsübergangsdiagramm & Finalzustände – Potenzautomat

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!


Andere Nutzer halten diese Inhalte aus dem Bereich „Theoretische Informatik“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.