Potenzmengenkonstruktion: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(23 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 8: Zeile 8:
Aber das Zentralabitur will die Informatik-Schüler in NRW trotzdem damit beglücken...
Aber das Zentralabitur will die Informatik-Schüler in NRW trotzdem damit beglücken...


=Wozu?=
=Erklärvideos=
 
* [https://www.youtube.com/watch?v=jq0gMxOrKUw NEA zu DEA Transformation]<br/>''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...''


Mithilfe der Potenzmengenkonstruktion kann man einen '''[[Deterministischer Endlicher Automat|Deterministischen Endlicher Automat]]&nbsp;  (DEA)''' in einen '''[[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]]&nbsp; (NEA)''' überführen.
* [https://youtu.be/LS_mCNlYvRY Potenzmengenkonstruktion (Klausurschreibweise)]<br/>''Das lohnt sich aber erst <u>nachträglich</u>, d.h. zur Klausurvorbereitung, anzuschauen!''


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


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...
=Wozu?=
[[Datei:DEA-RG-NEA-reg-Sprache.png|400px|thumb|right|Beziehungen: Reguläre Grammatik - DEA - NEA - reguläre Sprache]]
Mithilfe der Potenzmengenkonstruktion kann man einen '''[[Nicht-deterministischer endlicher Automaten|Nicht-deterministischen endlichen Automaten]]&nbsp; (NEA)'''  in einen '''[[Deterministischer Endlicher Automat|Deterministischen Endlicher Automat]]&nbsp;  (DEA)''' überführen.


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


Ein Zustand des DEA fasst all diejenigen Zustände des NEA zusammen, in denen sich der NEA zu einem bestimmten Zeitpunkt befinden könnte.
Die Grundidee ist reichlich abstrakt und hier - mit Absicht - sehr kurz gehalten. <br/>Man kann das sowieso erst verstehen, wenn man mal ein Beispiel durchexerziert hat...<br/><br/>
Also:<br/>
Der '''NEA''' kann sich bei gleicher Zeichenfolge "zeitgleich" in mehreren verschiedenen Zuständen befinden - <br/>je nachdem, welchen "Weg" man bei einem nicht-deterministischen Übergang gewählt hat.<br/><br/>
Ein Zustand des '''DEA''' fasst all diejenigen Zustände des '''NEA''' zusammen, <br/>in denen sich der '''NEA''' <u>zu einem bestimmten Zeitpunkt</u> befinden könnte.


=Beispiel=
=Beispiel=


==Youtube-Tutorial==
Das folgende Beispiel kommt von '''[https://de.wikipedia.org/wiki/Potenzmengenkonstruktion#Automat_zum_regulären_Ausdruck_(a|b)*aba Potenzmengenkonstruktion Wikipedia]''' und ist dort unter der [https://creativecommons.org/licenses/by-sa/3.0/legalcode CC BY-SA 3.0] veröffentlicht.
 


Wer Youtube-Erklärungen mag, ist hier richtig: '''[https://www.youtube.com/watch?v=jq0gMxOrKUw NEA zu DEA Transformation (Youtube)]'''. <br/>''Man muss aber 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...''
==Ausführliche Darstellung==


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


Das folgende Beispiel kommt von '''[https://de.wikipedia.org/wiki/Potenzmengenkonstruktion#Automat_zum_regulären_Ausdruck_(a|b)*aba Potenzmengenkonstruktion Wikipedia]''' und ist dort unter der [https://creativecommons.org/licenses/by-sa/3.0/legalcode CC BY-SA 3.0] veröffentlicht.
Für die Klausur (und für Hausaufgaben) bietet sich die Klausurschreibweise an, die weiter unten dargestellt wird.


===Ausgangspunkt===
===Ausgangspunkt===
Zeile 37: Zeile 46:


Von <math>s_0</math> aus kann man mit dem Buchstaben '''a''' zu zwei verschiedenen Zuständen (<math>s_0</math> und <math>s_1</math>) kommen; <br/>deswegen ist der Automat <u>nicht</u>-deterministisch.
Von <math>s_0</math> aus kann man mit dem Buchstaben '''a''' zu zwei verschiedenen Zuständen (<math>s_0</math> und <math>s_1</math>) kommen; <br/>deswegen ist der Automat <u>nicht</u>-deterministisch.
===Übergangsfunktion des '''NEA'''===
===Übergangsfunktion des '''NEA'''===


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


* <math>\mathcal{NEA} = (Q, A, \delta, S, E )</math>
* NEA = (A, Z, d, q<sub>0</sub>, E )<br/>''Eselsbrücke:''<br/>'''''A'''llen '''Z'''uhörern '''d'''oofen '''Q'''uatsch '''e'''rzählen''
* Alphabet: <math>A\!\, = \{a, b\}</math>
* '''A'''lphabet: A = <math> \{a, b\}</math>
* Menge der Zustände: <math>Q = \{s_0, s_1, s_2, s_3\}</math>
* Menge der '''Z'''ustände: Z = <math> \{s_0, s_1, s_2, s_3\}</math>


* Startzustand: <math>S = s_0</math>
* Startzustand: q<sub>0</sub><math>= s_0</math>
* Menge der Endzustände: <math>E = \{s_3\}</math>
* Menge der '''E'''ndzustände: E = <math>\{s_3\}</math>
* tabellarische Übertragungsfunktion <math>\delta\!\,</math>:
* Übergangsfunktion (in Tabellenform):<br/>'''d''':


{| class="wikitable" style="margin-left:2em"
{| class="wikitable" style="margin-left:2em"
Zeile 60: Zeile 68:
|<math>s_2\!\,</math>    ||<math>\{s_3\}\!\,</math>      ||<math>\emptyset</math>
|<math>s_2\!\,</math>    ||<math>\{s_3\}\!\,</math>      ||<math>\emptyset</math>
|-
|-
|<math>s_3\!\,</math>    ||<math>\emptyset</math>    ||<math>\emptyset</math>
|<math>s_3\!\,~~(E)</math>    ||<math>\emptyset</math>    ||<math>\emptyset</math>
|}
|}
''Hinweis: <math>\emptyset</math> ist die leere Menge.''
''Hinweise: ''
 
* ''<math>\emptyset</math> ist die leere Menge.''
 
* ''<math>(E)</math> bezeichnet einen Endzustand.''<br/>''Hier gibt es nur einen Endzustand, es kann aber mehrere geben!''


Man sieht also:<br/>
Man sieht also:<br/>
Zeile 73: Zeile 85:
{| class="wikitable" style="margin-left:2em"
{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
|- class="hintergrundfarbe6"
! DEA !! a !! b
! NEA -> DEA !! a !! b
|-
|-
|<math>S_0\!\, = \{s_0\}</math>          ||<math>\{s_0, s_1\}\!\,</math>      ||<math>\{s_0\}\!\,</math>
|<math>S_0\!\, = \{s_0\}</math>          ||<math>\{s_0, s_1\}\!\,</math>      ||<math>\{s_0\}\!\,</math>
Zeile 81: Zeile 93:
|<math>S_2\!\, = \{s_0, s_2\}</math>      ||<math>\{s_0, s_1, s_3\}\!\,</math> ||<math>\{s_0\}\!\,</math>
|<math>S_2\!\, = \{s_0, s_2\}</math>      ||<math>\{s_0, s_1, s_3\}\!\,</math> ||<math>\{s_0\}\!\,</math>
|-
|-
|<math>S_3\!\, = \{s_0, s_1, s_3\}</math> ||<math>\{s_0, s_1\}\!\,</math>      ||<math>\{s_0, s_2\}\!\,</math>
|<math>S_3\!\, = \{s_0, s_1, s_3\}~~(E)</math> ||<math>\{s_0, s_1\}\!\,</math>      ||<math>\{s_0, s_2\}\!\,</math>
|}
|}
Damit ein Zustand des '''DEA''' ein Endzustand ist, muss er mindestens einen Endzustand des '''NEA''' enthalten. <br/>''(Denn im '''NEA''' reicht es für das Erkennen eines Wortes, wenn es "mindestens einen Weg gibt".''
''Hinweis: <math>(E)</math> bezeichnet einen Endzustand.''


'''Wie kommt man darauf???'''
'''Wie kommt man darauf???'''
Die Übergangsfunktion baut man '''zeilenweise''' auf:
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.
* In der 1. Zeile steht als Ausgangszustand (d.h. ganz links) eine Menge, die nur den Startzustand des '''NEA''' enthält.


Zeile 106: Zeile 116:


* usw.
* usw.
* Die '''Endzustände''' sind genau die Zustände, die einen Endzustand des NEA enthalten. <br/>Das sind hier genau die Zustände, die <math>s_3</math> enthalten, also nur <math>S_3</math>


===Endzustände des DEA===
===Endzustände des DEA===


Im Beispiel ergibt sich als Menge der Endzustände <math>E\!\,' = \{S_3\}</math> , da nur <math>S_3\!\, = \{s_0, s_1, s_3\}</math> den Endzustand <math>s_3\!\,</math> des '''NEA''' enthält.
Damit ein Zustand des '''DEA''' ein Endzustand ist, muss er mindestens einen Endzustand des '''NEA''' enthalten. <br/>
''(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>E\!\,' = \{S_3\}</math> , <br/>da nur <math>S_3\!\, = \{s_0, s_1, s_3\}</math> den Endzustand <math>s_3\!\,</math> des '''NEA''' enthält.


===Übergangsfunktion des '''DEA'''===
===Übergangsfunktion des '''DEA'''===
Zeile 130: Zeile 145:
===Übergangsgraph des DEA===
===Übergangsgraph des DEA===
Insgesamt ergibt sich der deterministische Automat <math>\mathcal{A} = (Q', A, \delta', s_0', E')</math>, der folgende graphische Darstellung besitzt:
Insgesamt ergibt sich der deterministische Automat <math>\mathcal{A} = (Q', A, \delta', s_0', E')</math>, der folgende graphische Darstellung besitzt:
[[Datei:Potenzmengenkonstruktion-DEA.png]]
==Klausurschreibweise==
Hier wird dargestellt, wie man die Potenzmengenkonstruktion effizient darstellen kann.
<font color='red'>Diese Schreibweise ist am SIBI erlaubt. Andere Schulen können das durchaus anders (und formal anspruchsvoller) verlangen.</font>
Die wesentlichen Unterschiede sind:
# die Zustände des ursprünglichen Automaten durch Ziffern abkürzen.
# Zustandsmengen ohne geschweifte Klammern
# Zustände des entstehenden DEA direkt in die Tabelle eintragen, in einer anderen Farbe.<br/>Dafür...
## zuerst die Zustandsmengen in der linken Spalte von oben nach unten "durchnummerieren" (mit <font color='red'>S<sub>0</sub></font> bis <font color='red'>S<sub>3</sub></font>),
## dann die Zustandsmengen im Rest der Tabelle eintragen.<br/>Das erleichtert erheblich das Zeichnen des entstehenden DEA!
{| class="wikitable" style="margin-left:2em"
|- class="hintergrundfarbe6"
! NEA -> DEA !! a !! b
|-
|<font color='red'>S<sub>0</sub></font> = 0 ||<font color='red'>S<sub>1</sub></font> = 0, 1      ||<font color='red'>S<sub>0</sub></font> = 0
|-
|<font color='red'>S<sub>1</sub></font>= 0, 1||<font color='red'>S<sub>1</sub></font> = 0, 1||<font color='red'>S<sub>2</sub></font> = 0, 2
|-
|<font color='red'>S<sub>2</sub></font> = 0, 2||<font color='red'>S<sub>3</sub></font> = 0, 1, 3||<font color='red'>S<sub>0</sub></font> = 0
|-
|<font color='red'>S<sub>3</sub></font> = 0, 1, 3&nbsp;&nbsp;(E)||<font color='red'>S<sub>1</sub></font> = 0, 1||<font color='red'>S<sub>2</sub></font> = 0, 2
|}
''Hinweis: (E) bezeichnet einen Endzustand.''
'''entstehender DEA:'''


[[Datei:Potenzmengenkonstruktion-DEA.png]]
[[Datei:Potenzmengenkonstruktion-DEA.png]]

Aktuelle Version vom 24. Oktober 2023, 16:42 Uhr


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

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:

Potenzmengenkonstruktion-NEA.png

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, q0, 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: q0[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:

Potenzmengenkonstruktion-DEA.png

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 S0 bis S3),
    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:

Potenzmengenkonstruktion-DEA.png