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 16)
(Aufgabe 16)
Zeile 137: Zeile 137:
  
 
===Aufgabe 16===
 
===Aufgabe 16===
''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (<u>&Sigma;,V,S,P</u>), wobei <u> &Sigma</u> ein <u> Alphabet</u>, <u>V</u>
+
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (<u>&Sigma;,V,S,P</u>), wobei <u> &Sigma;</u> ein <u> Alphabet</u>, <u>V</u> eine Menge von <u> Variablen</u>, <u>S</u> die <u> Startvariable</u> und <u> P </u> eine Menge von <u> Produktionsregeln </u> ist.
 +
:Die Klasse der regulären Sprachen enthält Sprachen, die über <u>...</u> Grammatiken gebildet werden können. Eine Grammatik heißt <u>...</u>, wenn alle ihre Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Eigenschaften u &isin; <u> V </u> sowie ''v'' &isin; <u> &Sigma; </u> oder ''v'' &isin; <u> &Sigma; &omicron; V </u> erfüllen.
  
 
===Aufgabe 17===
 
===Aufgabe 17===

Version vom 22. Januar 2006, 14:58 Uhr

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

Lückentext: Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik G ist ein Tupel G = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
Die Klasse der regulären Sprachen enthält Sprachen, die über ... Grammatiken gebildet werden können. Eine Grammatik heißt ..., wenn alle ihre Produktionsregeln uvP die Eigenschaften u ∈ V sowie v Σ oder v Σ ο V erfüllen.

Aufgabe 17