Lösungen TheGI TI Probeklausur vom 19.01.06: Unterschied zwischen den Versionen

Version vom 22. Januar 2006, 14:32 Uhr

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...

Inhaltsverzeichnis

1 Aufgabe 1
2 Aufgabe 2
3 Aufgabe 3
4 Aufgabe 4
5 Aufgabe 5
6 Aufgabe 6
7 Aufgabe 7
8 Aufgabe 8,9,10
9 Aufgabe 11

Aufgabe 1

im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

Aufgabe 2

a ∈ Σ	Σⁱ = Σ	ε ∉ Σ⁺	ε ∈ Σ*
ø ⊆ Σ⁺	ø ⊆ Σ*	a ∈ Σ*	{ε} ∉ Σ*
Σ² ⊆ Σ*	ø ∈ P(Σ*)	{ε} ∈ P(Σ*)	Σ² ∈ P(Σ*)

{aa,bb,ab,ba} = Σ²	{xab : x ∈ Σ} = {x ∈ Σ : x endet mit ab}
{ab,bb,aba} ⊆ Σ*	{axab : x ∈ Σ} ⊆ {x ∈ Σ : x endet mit ab}

Aufgabe 3

{x ∈ Σ*; x beginnt mit a und endet mit b}
{x ∈ Σ*; x beginnt mit a oder b}
{x ∈ Σ*; x beginnt mit a oder b oder ist das leere Wort}
{x ∈ Σ*; x beginnt nicht mit a}
{ø,{a},{b},{a,b}}
{(a,a),(a,b),(b,a),(b,b)}

Aufgabe 4

hier müßte man irgendwie Bilder hochladen können...

Aufgabe 5

a) L₂ = {x ∈ Σ*; x beginnt mit ab}

b)

	a	b
→q₀	q₁	q₃
q₁	q₃	q₂
*q₂	q₂	q₂
q₃	q₃	q₃

c) einfach nur normale und Endzustände vertauschen

Aufgabe 6

a) L₃ = {x ∈ Σ*; x = (aⁿb)*a^m; n,m ≥ 1} über diese Lösung wurde lange diskutiert

b)

	a	b
→q₀	q₁	-
*q₁	q₁	q₀

c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q₂ hinzufügen, der von q₀ aus mit dem b erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

Aufgabe 7

a) L₄ = {x ∈ Σ*; x endet mit a}

b) bild einfügen

c)

	a	b
→q₀	{q₁,q₀}	{q₀}
*q₁	ø	ø

Aufgabe 8,9,10

Lösungen werden in einer kommenden Vorlesung nachgereicht

Aufgabe 11

(Fortsetzung des Ansatzes) Da das Wort w mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von w ein Zustand in A mindestens 2x besucht worden sein. Sei q_s der erste Zustand in der Ableitung von w, bei dem dies auftritt.

Zerlege w wie folgt: w=xyz mit:

x ist das Wort, welches bis zum ersten Auftreten von q_s von A gelesen wird.
y ist das Wort, welches vom Automaten in der Schleife von q_s nach q_s gelesen wird.
z ist der Rest des Wortes w.

Es gelten die drei Eigenschaften des Pumping-Lemmas:

y ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
|xy| < n : gilt, da wir die erste Schleife in A gewählt haben.
xy^kz in L : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

@@ Zeile 113: / Zeile 113: @@
 : Es gelten die drei Eigenschaften des Pumping-Lemmas:
 :#''y'' &ne; &epsilon; : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
-:#''xy'' &lt; ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
+:#''|xy|'' &lt; ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
 :#''xy''<sup>k</sup>''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.