Potenzmengenkonstruktion

Schon die Überschrift verspricht eine komplizierte, mühsame und langwierige Prozedur - und so ist es leider auch.

Aber das Zentralabitur will die Informatik-Schüler in NRW trotzdem damit beglücken...

Erklärvideos

• NEA zu DEA Transformation
  Man muss mindestens 17 Minuten Zeit haben, um die beiden Teile des Tutorials anzusehen! Und um es richtig zu verstehen, muss man vermutlich ab und zu nochmal zurückspulen...

• Potenzmengenkonstruktion (Klausurschreibweise)
  Das lohnt sich aber erst nachträglich, d.h. zur Klausurvorbereitung, anzuschauen!

Fachbegriffe

Nicht-deterministischer endlicher Automat (NEA), Deterministischer endlicher Automat (DEA), Zustandsübergangsfunktion (als Tabelle), Potenzmenge

Wozu?

Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache

Mithilfe der Potenzmengenkonstruktion kann man einen Nicht-deterministischen endlichen Automaten  (NEA) in einen Deterministischen Endlicher Automat  (DEA) überführen.

Grundidee

Die Grundidee ist reichlich abstrakt und hier - mit Absicht - sehr kurz gehalten.
Man kann das sowieso erst verstehen, wenn man mal ein Beispiel durchexerziert hat...

Also:
Der NEA kann sich bei gleicher Zeichenfolge "zeitgleich" in mehreren verschiedenen Zuständen befinden -
je nachdem, welchen "Weg" man bei einem nicht-deterministischen Übergang gewählt hat.

Ein Zustand des DEA fasst all diejenigen Zustände des NEA zusammen,
in denen sich der NEA zu einem bestimmten Zeitpunkt befinden könnte.

Beispiel

Das folgende Beispiel kommt von Potenzmengenkonstruktion Wikipedia und ist dort unter der CC BY-SA 3.0 veröffentlicht.

Ausführliche Darstellung

Die folgende Darstellung ist dafür gedacht, dass man die Potenzmengenkonstruktion gut versteht!

Für die Klausur (und für Hausaufgaben) bietet sich die Klausurschreibweise an, die weiter unten dargestellt wird.

Ausgangspunkt

Gegeben sei der folgende NEA:

Von [math]\displaystyle{ s_0 }[/math] aus kann man mit dem Buchstaben a zu zwei verschiedenen Zuständen ([math]\displaystyle{ s_0 }[/math] und [math]\displaystyle{ s_1 }[/math]) kommen;
deswegen ist der Automat nicht-deterministisch.

Übergangsfunktion des NEA

Der NEA lässt sich mithilfe einer Übergangsfunktion so beschreiben:

• NEA = (A, Z, d, q₀, E )
  Eselsbrücke:
  Allen Zuhörern doofen Quatsch erzählen
• Alphabet: A = [math]\displaystyle{ \{a, b\} }[/math]
• Menge der Zustände: Z = [math]\displaystyle{ \{s_0, s_1, s_2, s_3\} }[/math]

• Startzustand: q₀[math]\displaystyle{ = s_0 }[/math]
• Menge der Endzustände: E = [math]\displaystyle{ \{s_3\} }[/math]
• Übergangsfunktion (in Tabellenform):
  d:

NEA	a	b
[math]\displaystyle{ s_0\!\, }[/math]	[math]\displaystyle{ \{s_0\!\,, s_1\} }[/math]	[math]\displaystyle{ \{s_0\}\!\, }[/math]
[math]\displaystyle{ s_1\!\, }[/math]	[math]\displaystyle{ \emptyset }[/math]	[math]\displaystyle{ \{s_2\}\!\, }[/math]
[math]\displaystyle{ s_2\!\, }[/math]	[math]\displaystyle{ \{s_3\}\!\, }[/math]	[math]\displaystyle{ \emptyset }[/math]
[math]\displaystyle{ s_3\!\,~~(E) }[/math]	[math]\displaystyle{ \emptyset }[/math]	[math]\displaystyle{ \emptyset }[/math]

Hinweise:

• [math]\displaystyle{ \emptyset }[/math] ist die leere Menge.

• [math]\displaystyle{ (E) }[/math] bezeichnet einen Endzustand.
  Hier gibt es nur einen Endzustand, es kann aber mehrere geben!

Man sieht also:
Mit jedem Übergang kann man mehrere Zustände erreichen; diese werden als Menge von Zuständen angegeben.

Konstruktion des zugehörigen DEA

Die Zustandsmenge [math]\displaystyle{ Q\!\,' = \{S_0, S_1, S_2, S_3\} }[/math] und die Übertragungsfunktion [math]\displaystyle{ \delta\!\,' }[/math] des äquivalenten DEA ergibt sich wie folgt:

NEA -> DEA	a	b
[math]\displaystyle{ S_0\!\, = \{s_0\} }[/math]	[math]\displaystyle{ \{s_0, s_1\}\!\, }[/math]	[math]\displaystyle{ \{s_0\}\!\, }[/math]
[math]\displaystyle{ S_1\!\, = \{s_0, s_1\} }[/math]	[math]\displaystyle{ \{s_0, s_1\}\!\, }[/math]	[math]\displaystyle{ \{s_0, s_2\}\!\, }[/math]
[math]\displaystyle{ S_2\!\, = \{s_0, s_2\} }[/math]	[math]\displaystyle{ \{s_0, s_1, s_3\}\!\, }[/math]	[math]\displaystyle{ \{s_0\}\!\, }[/math]
[math]\displaystyle{ S_3\!\, = \{s_0, s_1, s_3\}~~(E) }[/math]	[math]\displaystyle{ \{s_0, s_1\}\!\, }[/math]	[math]\displaystyle{ \{s_0, s_2\}\!\, }[/math]

Hinweis: [math]\displaystyle{ (E) }[/math] bezeichnet einen Endzustand.

Wie kommt man darauf??? Die Übergangsfunktion baut man zeilenweise auf:

• In der 1. Zeile steht als Ausgangszustand (d.h. ganz links) eine Menge, die nur den Startzustand des NEA enthält.

• rechts daneben trägt man in den Spalten a und b ein: die Menge der Zustände, die man vom Startzustand aus mit a bzw. b erreichen kann.

• Dadurch hat sich in der Spalte a ein neuer Zustand ergeben: [math]\displaystyle{ \{s_0, s_1\}\!\, }[/math]
• Den trägt man in Zeile 2 ganz links als Ausgangszustand ein.

• Dann muss man sich überlegen, welche Zustände man von [math]\displaystyle{ s_0 }[/math] und [math]\displaystyle{ s_1 }[/math] aus im NEA erreichen kann:
  • Mit dem Zeichen a die Zustände [math]\displaystyle{ s_0 }[/math] und [math]\displaystyle{ s_1 }[/math]
  • mit dem Zeichen b die Zustände [math]\displaystyle{ s_0 }[/math] und [math]\displaystyle{ s_2 }[/math].
• Diese trägt man als Mengen in die Tabelle ein.

• Jetzt hat man noch einen neuen Zustand in der Spalte b: [math]\displaystyle{ \{s_0, s_2\}\!\, }[/math]

• Der ist dann ein weiterer Ausgangszustand und wird in der nächsten Zeile ganz links eingetragen.

• usw.

• Die Endzustände sind genau die Zustände, die einen Endzustand des NEA enthalten.
  Das sind hier genau die Zustände, die [math]\displaystyle{ s_3 }[/math] enthalten, also nur [math]\displaystyle{ S_3 }[/math]

Endzustände des DEA

Damit ein Zustand des DEA ein Endzustand ist, muss er mindestens einen Endzustand des NEA enthalten.
(Denn im NEA reicht es für das Erkennen eines Wortes, wenn es "mindestens einen Weg gibt".)

Im Beispiel ergibt sich als Menge der Endzustände [math]\displaystyle{ E\!\,' = \{S_3\} }[/math] ,
da nur [math]\displaystyle{ S_3\!\, = \{s_0, s_1, s_3\} }[/math] den Endzustand [math]\displaystyle{ s_3\!\, }[/math] des NEA enthält.

Übergangsfunktion des DEA

Die Übergangsfunktion des DEA lässt sich jetzt mit den Zuständen
[math]\displaystyle{ S_0\!\, = \{s_0\}, }[/math]  [math]\displaystyle{ S_1\!\, = \{s_0, s_1\}, }[/math]  [math]\displaystyle{ S_2\!\, = \{s_0, s_2\}, }[/math]  [math]\displaystyle{ S_3\!\, = \{s_0, s_1, s_3\} }[/math]
so darstellen:

DEA	a	b
[math]\displaystyle{ S_0 }[/math]	[math]\displaystyle{ S_1 }[/math]	[math]\displaystyle{ S_0 }[/math]
[math]\displaystyle{ S_1 }[/math]	[math]\displaystyle{ S_1 }[/math]	[math]\displaystyle{ S_2 }[/math]
[math]\displaystyle{ S_2 }[/math]	[math]\displaystyle{ S_3 }[/math]	[math]\displaystyle{ S_0 }[/math]
[math]\displaystyle{ S_3 }[/math]	[math]\displaystyle{ S_1 }[/math]	[math]\displaystyle{ S_2 }[/math]

Übergangsgraph des DEA

Insgesamt ergibt sich der deterministische Automat [math]\displaystyle{ \mathcal{A} = (Q', A, \delta', s_0', E') }[/math], der folgende graphische Darstellung besitzt:

Klausurschreibweise

Hier wird dargestellt, wie man die Potenzmengenkonstruktion effizient darstellen kann.

Diese Schreibweise ist am SIBI erlaubt. Andere Schulen können das durchaus anders (und formal anspruchsvoller) verlangen.

Die wesentlichen Unterschiede sind:

1. die Zustände des ursprünglichen Automaten durch Ziffern abkürzen.
2. Zustandsmengen ohne geschweifte Klammern
3. Zustände des entstehenden DEA direkt in die Tabelle eintragen, in einer anderen Farbe.
   Dafür...
   1. zuerst die Zustandsmengen in der linken Spalte von oben nach unten "durchnummerieren" (mit S₀ bis S₃),
   2. dann die Zustandsmengen im Rest der Tabelle eintragen.
      Das erleichtert erheblich das Zeichnen des entstehenden DEA!

NEA -> DEA	a	b
S0 = 0	S1 = 0, 1	S0 = 0
S1= 0, 1	S1 = 0, 1	S2 = 0, 2
S2 = 0, 2	S3 = 0, 1, 3	S0 = 0
S3 = 0, 1, 3  (E)	S1 = 0, 1	S2 = 0, 2

Hinweis: (E) bezeichnet einen Endzustand.

entstehender DEA: