Lösungen TheGI TI Probeklausur vom 19.01.06 - Versionsgeschichte

130.149.17.59: /* Aufgabe 3 */

2011-02-16T11:52:34Z

Aufgabe 3

← Nächstältere Version		Version vom 16. Februar 2011, 11:52 Uhr
Zeile 30:		Zeile 30:
	===Aufgabe 3===		===Aufgabe 3===
	# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} <br> auch: {''axb'' : ''x'' ∈ Σ*}		# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} <br> auch: {''axb'' : ''x'' ∈ Σ*}
	# {''x'' ∈ Σ+ : ''x'' beginnt mit ''a'' oder ''b''}		# {''x'' ∈ Σ<sup>+</sup> : ''x'' beginnt mit ''a'' oder ''b''}
	# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}		# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
	# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}		# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}

130.149.17.59: /* Aufgabe 3 */

2011-02-16T11:51:35Z

Aufgabe 3

← Nächstältere Version		Version vom 16. Februar 2011, 11:51 Uhr
Zeile 30:		Zeile 30:
	===Aufgabe 3===		===Aufgabe 3===
	# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} <br> auch: {''axb'' : ''x'' ∈ Σ*}		# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' und endet mit ''b''} <br> auch: {''axb'' : ''x'' ∈ Σ*}
	# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b''}		# {''x'' ∈ Σ+ : ''x'' beginnt mit ''a'' oder ''b''}
	# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}		# {''x'' ∈ Σ* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
	# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}		# {''x'' ∈ Σ* : ''x'' beginnt nicht mit ''a''}

Bastla: format + typo

2010-02-11T02:10:08Z

format + typo

← Nächstältere Version		Version vom 11. Februar 2010, 02:10 Uhr
Zeile 163:		Zeile 163:
	====10====		====10====

	R+S = S+R (Richtig, braucht ~~keines Nachweises~~)		(1) R+S = S+R (Richtig, braucht keinen Nachweis)

	RS = SR (Falsch, braucht ~~keines Nachweises~~)		(2) RS = SR (Falsch, braucht keinen Nachweis)

	(RS)* = (RS)* (Falsch)		(3) (RS)* = (RS)* (Falsch)
	Angenommen es gilt: Da (RS)=(R+S), muss gelten (RS)=(R+S) -		Angenommen es gilt: Da (RS)=(R+S), muss gelten (RS)=(R+S) -
	Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!		Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

	(R+S)* = (R+S)* (Richtig)		(4) (R+S)* = (R+S)* (Richtig)
	Direkter Beweis: (R+S)* = (RS)*		Direkter Beweis: (R+S)* = (RS)*
	= ((R)(S))*		= ((R)(S))*
	= (R+S)*		= (R+S)*

	===Aufgabe 11===		===Aufgabe 11===

Bastla: format

2010-02-11T02:07:50Z

format

← Nächstältere Version		Version vom 11. Februar 2010, 02:07 Uhr
Zeile 162:		Zeile 162:

	====10====		====10====
	R+S=S+R (Richtig, braucht keines Nachweises)
			R+S = S+R (Richtig, braucht keines Nachweises)

	RS=SR (Falsch, braucht keines Nachweises)		RS = SR (Falsch, braucht keines Nachweises)

	(RS)= (RS) (Falsch)		(RS)* = (RS)* (Falsch)
	Angenommen es gilt: Da (RS)=(R+S), muss gelten (RS)=(R+S)~~, mit~~ (RS)* ~~laesst~~ sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!		Angenommen es gilt: Da (RS)=(R+S), muss gelten (RS)=(R+S) -
			Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!

	(R+S)=(R+S) (Richtig)		(R+S)* = (R+S)* (Richtig)
	Direkter Beweis: (R+S)=(RS)=((R)(S))=(R+S)		Direkter Beweis: (R+S)* = (RS)*
			= ((R)(S))*
			= (R+S)*

	===Aufgabe 11===		===Aufgabe 11===

Bastla: typo

2010-02-11T01:58:52Z

typo

← Nächstältere Version		Version vom 11. Februar 2010, 01:58 Uhr
Zeile 159:		Zeile 159:
	F2 = (aab)E*		F2 = (aab)E*
	= aab(ab)*		= aab(ab)*
	F3 = (aab)+ (Iteration ~~setz mind.~~ das einmalige Vorkommen voraus)		F3 = (aab)+ (Iteration setzt mindestens das einmalige Vorkommen voraus)

	====10====		====10====

Bastla: hübscher

2010-02-11T01:57:26Z

hübscher

← Nächstältere Version		Version vom 11. Februar 2010, 01:57 Uhr
Zeile 155:		Zeile 155:

	====9====		====9====
	F1=E(aab)E=(ab)aab(ab)		F1 = E(aab)E
	F2=~~aabE~~=aab(ab)		= (ab)aab(ab)
	F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)		F2 = (aab)E*
			= aab(ab)*
			F3 = (aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)

	====10====		====10====

Bastla: format

2010-02-11T01:47:45Z

format

← Nächstältere Version		Version vom 11. Februar 2010, 01:47 Uhr
Zeile 145:		Zeile 145:

	====8====		====8====
	L1={x aus E* : in x kommt a mind. einmal vor}
	L2={x aus E* : x fängt mit a oder endet mit b}		L1 = {x aus E* : in x kommt a mind. einmal vor}
	L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}		L2 = {x aus E* : x fängt mit a oder endet mit b}
	L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}		L3 = {x aus {aa, bb}*}
	L5={e}		= {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
			L4 = {x aus (ab)*}
			= {x : x ist die Iteration des Strings ab oder das leere Wort}
			L5 = {ε}

	====9====		====9====

Bastla: Ergänzung + typos

2010-02-11T01:16:30Z

Ergänzung + typos

← Nächstältere Version		Version vom 11. Februar 2010, 01:16 Uhr
Zeile 103:		Zeile 103:

	===Aufgabe 6===		===Aufgabe 6===
	:a) ''L<sub>3</sub>'' = {''x'' ∈ Σ; ''x'' = a(a+ba)}		:a) ''L<sub>3</sub>'' = {''x'' ∈ Σ; ''x'' = a(a+ba)} = {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
	:b)		:b)
	::{\| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"		::{\| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
Zeile 118:		Zeile 118:
	\|q<sub>0</sub>		\|q<sub>0</sub>
	\|}		\|}
	:c) Der Trick ist, dass der DEA erst in einen totalen DEA ~~umgeform~~ werden ~~muß~~. D.h. man ~~muß~~ einen Zustand q<sub>2</sub> hinzufügen, der von q<sub>0</sub> aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q<sub>2</sub> bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.		:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q<sub>2</sub> hinzufügen, der von q<sub>0</sub> aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q<sub>2</sub> bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

	===Aufgabe 7===		===Aufgabe 7===

Bastla: ja, kann man

2010-02-11T00:53:21Z

ja, kann man

← Nächstältere Version		Version vom 11. Februar 2010, 00:53 Uhr
Zeile 55:		Zeile 55:
	===Aufgabe 5===		===Aufgabe 5===

	:a) ''L<sub>2</sub>'' = {''x'' ∈ Σ*; ''x'' beginnt mit ''ab''}		:a) ''L<sub>2</sub>'' = {''abx'' \| x ∈ Σ} = {''x'' ∈ Σ; ''x'' beginnt mit ''ab''}
	~~kann man eigentlich auch~~
	~~''L<sub>2</sub>'' = {''abx'' \| x ∈ Σ*}~~
	~~schreiben?~~

	:b)		:b)

Bastla: typos und Formulierung angepasst

2010-02-11T00:10:34Z

typos und Formulierung angepasst

← Nächstältere Version		Version vom 11. Februar 2010, 00:10 Uhr
Zeile 258:		Zeile 258:

	===Aufgabe 18===		===Aufgabe 18===

	#		#
	#* Die Sprache L<sub>2</sub> ist komplementär zur Sprache L<sub>1</sub>		#* Die Sprache L<sub>2</sub> ist komplementär zur Sprache L<sub>1</sub>
Zeile 263:		Zeile 264:
	#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von M<sub>ω</sub>		#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von M<sub>ω</sub>
	#		#
	#* Eine Sprache ist entscheidbar, ~~wenn~~ wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.		#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
	#* Eine Sprache ist semi-entscheidbar, wenn ~~ein Automat für diese Sprache terminiert~~ für Wörter aus ~~der~~ Sprache, sein Zustand für Wörter die nicht aus der Sprache sind ~~aber~~ undefiniert ~~ist,~~ er möglicherweise ~~also~~ nicht ~~terminiert~~ für ~~Wörter die nicht aus der Sprache sind~~.		#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
	#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält.		#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
	#		#
	::{\| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"		::{\| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"