Lösungen TheGI TI Probeklausur vom 19.01.06

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

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

1. {x ∈ Σ*; x beginnt mit a und endet mit b}
2. {x ∈ Σ*; x beginnt mit a oder b}
3. {x ∈ Σ*; x beginnt mit a oder b oder ist das leere Wort}
4. {x ∈ Σ*; x beginnt nicht mit a}
5. {ø,{a},{b},{a,b}}
6. {(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){| border="1"

! !a !b |- |q₀ |q₁ |q₃ |- |q₁ |q₃ |q₂ |- |*q₂ |q₂ |q₂ |- |q₃ |q₃ |q₃ |}