Potenzmengenkonstruktion - Versionsgeschichte

Akaibel: /* Übergangsfunktion des NEA */

2023-10-24T16:42:00Z

Übergangsfunktion des NEA

← Nächstältere Version		Version vom 24. Oktober 2023, 16:42 Uhr
Zeile 56:		Zeile 56:
	* Startzustand: q<sub>0</sub><math>= s_0</math>		* Startzustand: q<sub>0</sub><math>= s_0</math>
	* Menge der '''E'''ndzustände: E = <math>\{s_3\}</math>		* Menge der '''E'''ndzustände: E = <math>\{s_3\}</math>
	* Übergangsfunktion (in Tabellenform): d:		* Übergangsfunktion (in Tabellenform):<br/>'''d''':

	{\| class="wikitable" style="margin-left:2em"		{\| class="wikitable" style="margin-left:2em"

Akaibel: /* Übergangsfunktion des NEA */

2023-10-24T16:40:51Z

Übergangsfunktion des NEA

← Nächstältere Version		Version vom 24. Oktober 2023, 16:40 Uhr
Zeile 50:		Zeile 50:
	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): d:

	{\| class="wikitable" style="margin-left:2em"		{\| class="wikitable" style="margin-left:2em"
Zeile 74:		Zeile 74:
	* ''<math>\emptyset</math> ist die leere Menge.''		* ''<math>\emptyset</math> ist die leere Menge.''

	* ''<math>(E)</math> bezeichnet einen Endzustand.''		* ''<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/>

Akaibel: /* Wozu? */

2022-02-14T19:16:57Z

Wozu?

← Nächstältere Version		Version vom 14. Februar 2022, 19:16 Uhr
Zeile 18:		Zeile 18:

	=Wozu?=		=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]]  (NEA)''' in einen '''[[Deterministischer Endlicher Automat\|Deterministischen Endlicher Automat]]  (DEA)''' überführen.		Mithilfe der Potenzmengenkonstruktion kann man einen '''[[Nicht-deterministischer endlicher Automaten\|Nicht-deterministischen endlichen Automaten]]  (NEA)''' in einen '''[[Deterministischer Endlicher Automat\|Deterministischen Endlicher Automat]]  (DEA)''' überführen.

Akaibel: /* Klausurschreibweise */

2021-02-23T19:20:17Z

Klausurschreibweise

← Nächstältere Version		Version vom 23. Februar 2021, 19:20 Uhr
Zeile 149:		Zeile 149:

	Hier wird dargestellt, wie man die Potenzmengenkonstruktion effizient darstellen kann.		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 wesentlichen Unterschiede sind:

Akaibel: /* Klausurschreibweise */

2021-02-23T19:18:54Z

Klausurschreibweise

← Nächstältere Version		Version vom 23. Februar 2021, 19:18 Uhr
Zeile 154:		Zeile 154:
	# Zustandsmengen ohne geschweifte Klammern		# Zustandsmengen ohne geschweifte Klammern
	# Zustände des entstehenden DEA direkt in die Tabelle eintragen, in einer anderen Farbe.<br/>Dafür...		# 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>),
	## zuerst die Zustandsmengen in der linken Spalte von oben nach unten "durchnummerieren" (mit S<sub>0</sub> bis S<sub>3</sub>),

	## dann die Zustandsmengen im Rest der Tabelle eintragen.<br/>Das erleichtert erheblich das Zeichnen des entstehenden DEA!		## dann die Zustandsmengen im Rest der Tabelle eintragen.<br/>Das erleichtert erheblich das Zeichnen des entstehenden DEA!
	{\| class="wikitable" style="margin-left:2em"		{\| class="wikitable" style="margin-left:2em"

	\|- class="hintergrundfarbe6"		\|- class="hintergrundfarbe6"
	! NEA -> DEA !! a !! b		! NEA -> DEA !! a !! b
Zeile 171:		Zeile 170:
	\|}		\|}
	''Hinweis: (E) bezeichnet einen Endzustand.''		''Hinweis: (E) bezeichnet einen Endzustand.''
	~~===Ergebnis===~~
			'''entstehender DEA:'''

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

Akaibel: /* Klausurschreibweise */

2021-02-23T19:17:07Z

Klausurschreibweise

← Nächstältere Version		Version vom 23. Februar 2021, 19:17 Uhr
Zeile 152:		Zeile 152:

	# die Zustände des ursprünglichen Automaten durch Ziffern abkürzen.		# die Zustände des ursprünglichen Automaten durch Ziffern abkürzen.

	# Zustandsmengen ohne geschweifte Klammern		# Zustandsmengen ohne geschweifte Klammern
			# Zustände des entstehenden DEA direkt in die Tabelle eintragen, in einer anderen Farbe.<br/>Dafür...

	# ~~Zustände des entstehenden DEA direkt~~ in ~~die Tabelle eintragen~~, ~~in einer anderen Farbe.~~		## zuerst die Zustandsmengen in der linken Spalte von oben nach unten "durchnummerieren" (mit S<sub>0</sub> bis S<sub>3</sub>),

			## dann die Zustandsmengen im Rest der Tabelle eintragen.<br/>Das erleichtert erheblich das Zeichnen des entstehenden DEA!
	{\| class="wikitable" style="margin-left:2em"		{\| class="wikitable" style="margin-left:2em"
	\|- class="hintergrundfarbe6"		\|- class="hintergrundfarbe6"
Zeile 165:		Zeile 166:
	\|<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>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
	\|-		\|-
	\|<~~math~~>~~S_2\!\, = \{s_0, s_2\}~~</~~math~~> \|\|<~~math~~>~~\{s_0, s_1, s_3\}\!\,~~</~~math~~> \|\|<~~math~~>~~\{s_0\}\!\,~~</~~math~~>		\|<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
	\|-		\|-
	\|<~~math~~>~~S_3\!\,~~ = ~~\{s_0~~, ~~s_1~~, ~~s_3\}~~~~(E)</~~math~~> \|\|<~~math~~>~~\{s_0, s_1\}\!\,~~<~~/math~~> \|\|<~~math~~>~~\{s_0, s_2\}\!\,~~</~~math~~>		\|<font color='red'>S<sub>3</sub></font> = 0, 1, 3  (E)\|\|<font color='red'>S<sub>1</sub></font> = 0, 1\|\|<font color='red'>S<sub>2</sub></font> = 0, 2
	\|}		\|}
	''Hinweis: ~~<math>~~(E)~~</math>~~ bezeichnet einen Endzustand.''		''Hinweis: (E) bezeichnet einen Endzustand.''
	===Ergebnis===		===Ergebnis===
	[[Datei:Potenzmengenkonstruktion-DEA.png]]		[[Datei:Potenzmengenkonstruktion-DEA.png]]

Akaibel: /* Klausurschreibweise */

2021-02-23T19:09:04Z

Klausurschreibweise

← Nächstältere Version		Version vom 23. Februar 2021, 19:09 Uhr
Zeile 161:		Zeile 161:
	! NEA -> DEA !! a !! b		! NEA -> DEA !! a !! b
	\|-		\|-
	\|~~<math>~~<font color='red'>~~S_0~~</~~font~~>~~\!\, = \{s_0\}~~</~~math~~> \|\|<~~math~~>~~\{s_0, s_1\}\!\,~~</~~math~~> \|\|<~~math~~>~~\{s_0\}\!\,~~</~~math~~>		\|<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
	\|-		\|-
	\|<~~math~~>~~S_1\!\, = \{s_0, s_1\}~~</~~math~~> \|\|<~~math~~>~~\{s_0, s_1\}\!\,~~</~~math~~> \|\|<~~math~~>~~\{s_0, s_2\}\!\,~~</~~math~~>		\|<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
	\|-		\|-
	\|<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>

Akaibel: /* Klausurschreibweise */

2021-02-23T19:02:04Z

Klausurschreibweise

← Nächstältere Version		Version vom 23. Februar 2021, 19:02 Uhr
Zeile 170:		Zeile 170:
	\|}		\|}
	''Hinweis: <math>(E)</math> bezeichnet einen Endzustand.''		''Hinweis: <math>(E)</math> bezeichnet einen Endzustand.''
			===Ergebnis===
			[[Datei:Potenzmengenkonstruktion-DEA.png]]

Akaibel: /* Beispiel */

2021-02-23T19:01:02Z

Beispiel

@@ Zeile 29: / Zeile 29: @@
 =Beispiel=
-==Konventionell==
+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.
-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===
@@ Zeile 40: / Zeile 45: @@
 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'''===
@@ Zeile 142: / Zeile 146: @@
 [[Datei:Potenzmengenkonstruktion-DEA.png]]

Akaibel: /* Erklärvideo */

2020-05-26T13:59:50Z

Erklärvideo

← Nächstältere Version		Version vom 26. Mai 2020, 13:59 Uhr
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...

	=~~Erklärvideo~~=		=Erklärvideos=

	* [https://www.youtube.com/watch?v=jq0gMxOrKUw NEA zu DEA Transformation ~~(Youtube)~~]<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...''		* [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...''

	* [https://youtu.be/LS_mCNlYvRY Potenzmengenkonstruktion (Klausurschreibweise)]<br/>''Das lohnt sich aber erst <u>nachträglich</u>, d.h. zur Klausurvorbereitung, anzuschauen!''		* [https://youtu.be/LS_mCNlYvRY Potenzmengenkonstruktion (Klausurschreibweise)]<br/>''Das lohnt sich aber erst <u>nachträglich</u>, d.h. zur Klausurvorbereitung, anzuschauen!''