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

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) 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} dies ist meine Lösung. Über diese Aufgabe wurde lange diskutiert ohne dass etwas Vernünftiges heraus kam.
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.

Aufgabe 7

a) L4 = {x ∈ Σ*; x endet mit a}
b) bild einfügen
c)
a b
→q0 {q1,q0} {q0}
*q1 ø ø

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 qs 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 qs von A gelesen wird.
  • y ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
  • z ist der Rest des Wortes w.
Es gelten die drei Eigenschaften des Pumping-Lemmas:
  1. y ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
  2. |xy| < n : gilt, da wir die erste Schleife in A gewählt haben.
  3. xykz in L : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

Aufgabe 12

a) wähle n=5
b) w=abaaa ; x=ab, y=a, z=aa; xy3z=abaaaaa

Aufgabe 13

(weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich w in w=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y|an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

Aufgabe 14

a) bilder...
b)
  1. S⇒ aS⇒ aaSbS⇒ aaaSbSbS⇒ aaabSbS⇒ aaabbS⇒ aaabb
  2. S⇒ aSbS⇒ aaSbS⇒ aaaSbSbS⇒ aaabSbS⇒ aaabbS⇒ aaabb

Aufgabe 15

von oben nach unten
  • Typ-0; allgemeine
  • Typ-1; kontext-sensitive
  • Typ-2; kontext-freie
  • Typ-3; reguläre

Aufgabe 16

Aufgabe 17