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) L₂ = {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) L₃ = {x ∈ Σ*; x = (aⁿb)*a^m; 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 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
→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 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:

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. xy^kz 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; xy³z=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 xy²z ∈ L. Für dieses Wort gilt aber xy²z = a^n-|y|a^|y|+|y|aⁿ. 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 u → v ∈ P die Eigenschaften u ∈ V sowie v ∈ Σ oder v ∈ Σ ο V erfüllen.