Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

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

(Aufgabe 6)
(Aufgabe 6)
Zeile 82: Zeile 82:
 
|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. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

Version vom 22. Januar 2006, 14:12 Uhr

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) L2 = {x ∈ Σ*; x beginnt mit ab}
b)
a b
q0 q1 q3
q1 q3 q2
*q2 q2 q2
q3 q3 q3
c) einfach nur normale und Endzustände vertauschen

Aufgabe 6

a) L3 = {x ∈ Σ*; x = (anb)*am; n,m ≥ 1} über diese Lösung wurde lange diskutiert
b)
a b
→q0 q1 -
*q1 q1 q0
c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q2 hinzufügen, der von q0 aus mit dem b erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.