Potenzmengenkonstruktion

Version vom 8. November 2026, 09:12 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Ein NEA lässt sich nicht direkt programmieren, weil er mehrere Wege gleichzeitig verfolgt. Die Potenzmengenkonstruktion macht daraus einen eindeutigen DEA. ==Definition== Die Potenzmengenkonstruktion ist ein Verfahren, das zu einem NEA einen gleichwertigen DEA konstruiert. Jeder Zustand…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Ein NEA lässt sich nicht direkt programmieren, weil er mehrere Wege gleichzeitig verfolgt. Die Potenzmengenkonstruktion macht daraus einen eindeutigen DEA.

Definition

Die Potenzmengenkonstruktion ist ein Verfahren, das zu einem NEA einen gleichwertigen DEA konstruiert. Jeder Zustand des DEA ist eine Menge von NEA-Zuständen. Das Verfahren heißt auch Teilmengenkonstruktion oder Myhill-Teilmengen-Verfahren.

Verfahren

Gegeben ist ein NEA [math]\displaystyle{ A = (Q, \Sigma, \delta, q0, F) }[/math]. Der DEA entsteht in fünf Schritten:

  1. Der Startzustand des DEA ist die Menge [math]\displaystyle{ \{q0\} }[/math].
  2. Für jede neue Menge [math]\displaystyle{ M }[/math] und jedes Zeichen [math]\displaystyle{ a \in \Sigma }[/math] wird die Vereinigung aller Folgezustände gebildet: [math]\displaystyle{ \delta'(M, a) = \bigcup_{q \in M} \delta(q, a) }[/math].
  3. Jede neue Menge, die dabei entsteht, wird als Zeile in die Tabelle aufgenommen. Das wiederholt sich, bis keine neue Menge mehr entsteht.
  4. Endzustände sind alle Mengen, die mindestens einen Endzustand des NEA enthalten.
  5. Die Tabelle wird in einen Übergangsgraphen übertragen.

Die Tabelle wird wie die Übergangstabelle eines DEA gelesen: Der Pfeil → markiert den Startzustand, der Stern * die Endzustände. Ist der Startzustand zugleich Endzustand, stehen beide Zeichen davor.

Fehlerzustand

Hat kein Zustand einer Menge für ein Zeichen einen Folgezustand, ist die Vereinigung die leere Menge [math]\displaystyle{ \emptyset }[/math]. Sie wird als Zustand qF geführt. Alle Zeichen bleiben in qF. qF ist kein Endzustand, denn von dort kann kein Pfad des NEA mehr erfolgreich sein. Erst mit qF ist der DEA vollständig.

Gleichwertigkeit von NEA und DEA

Nach dem Lesen eines Wortes [math]\displaystyle{ w }[/math] enthält die Menge, in der der DEA steht, genau die Zustände, die der NEA nach [math]\displaystyle{ w }[/math] erreichen kann. Deshalb erreicht der DEA einen Endzustand genau dann, wenn ein Pfad des NEA das tut. Der DEA akzeptiert [math]\displaystyle{ w }[/math] also genau dann, wenn der NEA es akzeptiert.

Umgekehrt ist jeder DEA ein NEA, bei dem jede Menge von Folgezuständen genau ein Element hat. Beide Automatenarten erkennen damit dieselben Sprachen.

Hat der NEA [math]\displaystyle{ n }[/math] Zustände, hat seine Potenzmenge [math]\displaystyle{ 2^n }[/math] Elemente. Der DEA kann deshalb bis zu [math]\displaystyle{ 2^n }[/math] Zustände haben. Meist entstehen weniger, weil nur die vom Start aus erreichbaren Mengen aufgenommen werden.

Umwandlung eines ε-NEA

Bei einem ε-NEA ist die Startmenge [math]\displaystyle{ E(q0) }[/math], der ε-Abschluss des Startzustands. Nach jedem Schritt wird der ε-Abschluss gebildet:

[math]\displaystyle{ \delta'(M, a) = E\left(\bigcup_{q \in M} \delta(q, a)\right) }[/math]

Alle übrigen Schritte bleiben wie im Abschnitt Verfahren. Der DEA hat keine ε-Übergänge mehr.

Beispiele

Spam-Filter in einen DEA überführen

 
Spam-Filter als NEA

Der NEA erkennt Nachrichten, die die Zeichenfolge UML enthalten. Seine Übergangstabelle steht im Beispiel Spam-Filter als NEA modellieren. Im Bild gilt: q0 führt bei U nach q0 und q1, bei M, L und x nur nach q0. q1 führt bei M nach q2, q2 führt bei L nach q3. q3 bleibt bei jedem Zeichen in q3.

Rechengang. Die erste Zeile der Tabelle ist die Startmenge {q0}. Für jede Menge und jedes Zeichen wird die Vereinigung der Folgezustände gebildet.

  • {q0} bei U: q0 führt bei U nach q0 und q1. Es gilt [math]\displaystyle{ \delta'(\{q0\}, U) = \{q0, q1\} }[/math].
  • {q0,q1} bei M: q0 führt bei M nach q0, q1 führt bei M nach q2. Es gilt [math]\displaystyle{ \delta'(\{q0, q1\}, M) = \{q0\} \cup \{q2\} = \{q0, q2\} }[/math].

Alle weiteren Zellen entstehen auf dieselbe Weise. Neue Mengen kommen als neue Zeilen hinzu, bis keine mehr entsteht. Das ergibt sechs Zustände:

Zustand U M L x
→ {q0} {q0,q1} {q0} {q0} {q0}
{q0,q1} {q0,q1} {q0,q2} {q0} {q0}
{q0,q2} {q0,q1} {q0} {q0,q3} {q0}
* {q0,q3} {q0,q1,q3} {q0,q3} {q0,q3} {q0,q3}
* {q0,q1,q3} {q0,q1,q3} {q0,q2,q3} {q0,q3} {q0,q3}
* {q0,q2,q3} {q0,q1,q3} {q0,q3} {q0,q3} {q0,q3}

Alle sechs Mengen enthalten q0, weil q0 bei jedem Zeichen wieder nach q0 führt. Die leere Menge entsteht nie, ein Fehlerzustand qF ist nicht nötig. Endzustände sind alle Mengen mit q3, also {q0,q3}, {q0,q1,q3} und {q0,q2,q3}.

Die drei Endzustände verhalten sich gleich: Jedes Zeichen führt wieder zu einer Menge mit q3. Sie lassen sich zu einem Zustand q3 zusammenlegen. Das Zusammenlegen gleichwertiger Zustände ist die Minimierung. Die anderen Mengen heißen dann q0 für {q0}, q1 für {q0,q1} und q2 für {q0,q2}.

Zustand U M L x
→ q0 q1 q0 q0 q0
q1 q1 q2 q0 q0
q2 q1 q0 q3 q0
* q3 q3 q3 q3 q3
 
Spam-Filter als DEA

Der DEA hat vier Zustände und akzeptiert dieselben Nachrichten wie der NEA, nämlich alle mit der Zeichenfolge UML.

ε-NEA in einen DEA überführen

 
DEA aus dem ε-NEA mit Fehlerzustand qF

Der Automat stammt aus dem Beispiel ε-Abschluss bestimmen. Von q0 führen ε-Übergänge nach q1 und q2. q1 liest a und bleibt in q1, q2 liest b und bleibt in q2. q1 und q2 sind Endzustände.

Startmenge. Die erste Zeile ist [math]\displaystyle{ E(q0) = \{q0, q1, q2\} }[/math].

Folgemengen der Startmenge.

  • Bei a hat nur q1 einen Übergang, er führt nach q1: [math]\displaystyle{ \delta'(\{q0, q1, q2\}, a) = E(\{q1\}) = \{q1\} }[/math].
  • Bei b hat nur q2 einen Übergang, er führt nach q2: [math]\displaystyle{ \delta'(\{q0, q1, q2\}, b) = E(\{q2\}) = \{q2\} }[/math].

Weitere Zeilen. Neue Mengen sind {q1} und {q2}. {q1} bleibt bei a in {q1}, bei b entsteht die leere Menge, also qF. {q2} führt bei a nach qF und bleibt bei b in {q2}. qF führt bei jedem Zeichen nach qF.

Endzustände. Jede Menge außer qF enthält q1 oder q2 und ist deshalb ein Endzustand.

Zustand a b
→ * {q0,q1,q2} {q1} {q2}
* {q1} {q1} qF
* {q2} qF {q2}
qF qF qF

Der DEA akzeptiert Wörter, die nur aus a oder nur aus b bestehen. Der Startzustand ist zugleich Endzustand, deshalb wird auch das leere Wort akzeptiert.