Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Lösungsversuch Klausur WS13/14
Hi,
zur Vorbereitung versuche ich mich gerade an der Altklausur vom letzten Semester.
Hier meine Ideen, ich bitte um Korrektur, wenn was falsch ist:
- Aufwärmfragen: (Bei denen bin ich mir sehr unsicher.)
a) Es gibt L1 und L2 mit: L1 und L2 sind kontextfrei und L1 ∩ L2 ist unentscheidbar.
Stimmt nicht. Der Schnitt zweier kontextfreien Sprachen ist mindestens kontextsensitiv.
b) Sei H das allgemeine Halteprobem und SAT das Erfullbarkeitsproblem. Es gilt: H ≤ SAT
Stimmt nicht. Somit wäre H entscheidbar. (danke an qwert)
c) Es gibt reguläre Sprachen L, sodass es L’, L’ ⊂ L mit: L’ ist unentscheidbar.
Stimmt. Jede Sprache ist Teilmenge einer Regulären Sprache. Sei L eine Sprache über ∑ und uentscheidbar. Dann ist ∑* eine reguläre Sprache.
a) H = {x | M gestartet mit x hält}
b) Reduktion. Hier hab ich folgende Frage: Reicht es aus, dass meine schlaue Maschine, die ich bei der Reduktionsfunktion zurück gebe, für eine Eingabe z.b. x = 1, 1 ausgibt, oder muss die schlaue Maschine für alle x x^2 ausgeben? Darf ich dann einfach schreiben: Eingabe x, starte M’ mit w, berechne bin(x), gib bin(x^2) aus.
a) ∃p ∈N: ∀z∈L, |z|≥p: ∃ u,v,w,x,y ∈ ∑*, uvwxy = z: (|vwx|≤p) ∧ (|vx|≥1) ∧ (∀i∈N₀: uv^iwx^iy ∈ L)
b) Wähle p = 8; z beliebig aber fest mit |z| ≥ p; Wähle x = ε, v = 0, w = 0000111, u = restliche 0, y = restliche 1 → für alle i werden 0en gepumpt, auch für i = 0 ist das Wort noch in L.
c) p beliebig aber fest, setze z = 0^(p+2)1^(p+1) 
^(p), uvwxy beliebig aber fest mit uvwxy = z, Annahme ersten zwei Bedingungen sind erfüllt, also (|vwx|≤p) ∧ (|vx|≥1).
Jetzt ist zu zeigen, (∃i∈N₀: uv^iwx^iy ∉ L)
Abhängig von v und x kann man jetzt entweder 0en bzw 1en wegpumpen, oder 1en bzw dazupumpen wodurch jeweils das Wort nicht mehr in L ist, da k > l > m > 0 verletzt wird.
a) L = {w in {a,b}* | w enthält bb}
b) (gibts ein Programm zum Automaten zeichnen?)
Rest kommt noch in nächster Zeit.
Wär cool wenn jemand der auch gerade dransitzt und für Montag lern, mal drüber schaun kann und evtl. Verbesserungsvorschläge bringt.
Grüße
Nenas
Edit: Titel geändert.
1 „Gefällt mir“
also ich kann zumindest schonmal für die 1.b) sagen, dass es nicht gilt. Denn wäre H auf SAT reduzierbar, so wäre H auf jeden Fall entscheidbar.
1 „Gefällt mir“
Hey ich bin auch gerade dabei Klausuren durchzurechnen.
1. Die sehen soweit richtig aus.
2. b)
H<=L2b
f(x) = { <FM<M>w>#1 wenn x = <M>w
0 sonst
FM:
Eingabe sei x
wenn x = #1
Starte M mit w
gib #1 aus und halte
Mu:
Eingabe sei x
laufe unendlich nach rechts
"=>"
x ∈ H => x =<M>w
=> FM<M>w hält
=> <FM<M>w>#1 ∈ L2b
"<=" ..
=> H <= L2b
Da H unentscheidbar ist es auch L2b.3. b)
Ich habe u=ε, v=0^(4+i), w=ε, x=1^(3+i), y=ε gesetzt. nl = 7
vx sind dann 0000111 >= 1, passt
vwx sind ebenso 0000111 <= 7 passt
Gepumpt für i=0 ists auch 0000111 in L.
c) Wie du schon geschrieben hast, kann man immer nur 2 der 3 verschiedenen Zeichen pumpen.
4. a) richtig.
b)
Ich habe dein {qf} bei mir {q0,q2} genannt. Sonst genauso.
c) In den Kommentaren…
5. Hier weiß ich nicht ob die Definitionen genau die sind die gefordert wurden.
a) (oberhalb Def.4.8)
g=µf(x1,…,xk) = min { n | f(n,x1,…xk)=0 und fürAlle m<n ist f(m,x1,…,xk) definiert }
b) f(x,y)=(9-3x)(y+1)
Edit: Nach cauca durchgehen des ersten parameters bis y=0. Das passiert bei x=3:
f(x, y) = 0, x = 3: (9-9)(y+1) = 0
c) Den Satz hab ich nicht in meinen Aufzeichnungen oder in den Onlineaufzeichnungen gefunden. Keine Ahnung wo man den her haben sollte:
Satz (Kleene):
f(x1,…,xn) = p(x1,…,xn, µq(x1,…,xn))
d)
mult(0,x) = null(x)
mult(n+1,x)=add(mult(n,x),x)
6. a)
VC={<G,k>| G ist ungerichteter Graph mit einer überdeckenden Knotenmenge von maximal k Knoten}
Überdeckende Knotenmenge heißt, dass mit max. K Knoten alle Kanten abgedeckt werden.
b) Reicht das so?
z.Z.: x ∈ ENDERIESIG ≤p CLIQUE
f(x) = <G,k> falls x ∈ ER,
0 falls x ∉ ER
ER ist in polynomialzeit entscheidbar. f ist total berechenbar => Reduktion in polynomialzeit.
x ∈ ER => f(x) ∈ CLIQUE
x ∉ ER => f(x) ∉ CLIQUE
c)
ER ∈ P, CLIQUE ∈ NP
NP-schwere von ER beweisen:
CLIQUE ≤p ER
f(x) = <1,2,3> wenn x=CLIQUE
0 sonst
x ∈ CLIQUE => f(x) = ER
x ∉ CLIQUE => f(x) ∉ ER
Da CLIQUE NP vollständig ist dann ER NP schwer.
CLIQUE ≤p ER
Nach Definition im Hefter ist dann CLIQUE ∈ P.
Da CLIQUE aus NP ist: P=NP
1 „Gefällt mir“
Ich habe die 6 mal noch reingeschrieben.
Gibt es irgendwo Übungsaufgaben mit Lösungen zu sonen µRekursiven Sachen wie bei 5. b)?
Nein gibts nicht, Blatt 14 vom WS1314 behandelt ein bisschen rekursive Funktionen, genauso wie die Präsenzaufgabe auf Blatt 13. Blatt 14 wurde aber nie in einer Übung oder so besprochen.
Für mich ist schon die Definition recht schwammig. Es wird nach einem n gesucht, für das f(n, x1, …,xn) = 0 ist. Ich versteh das so, dass z.b. bei der Funktion f(x, y) = (5-x) * (3-y), n=3 min ist. Also müsste laut Def. µf(x1,…,xk) = 3 sein, was wenig Sinn macht.
Ja vielleicht schaut jemand der Ahnung hat mal drüber. Ich hab die Ergebnisse noch ein wenig ergänzt. Aber leider kann ich auch nicht 100%ig sagen, dass das so stimmt…
Hat einer eine Idee wie die Mschlau bei 2b aussehen könnte?
Ich würd mal behaupten das so was in der Art reicht:
- Eingabe sei bin(x).
- Starte M mit w.
- Gib bin(x^2) aus.
Es ist ja bekannt, das eine det. 1-Band TM das berechnen kann, ich denk nicht, dass man da dann noch näher drauf eingehen muss.
Wieso wird nicht M mit w gestartet?
1 „Gefällt mir“
Weil Namen Schall und Rauch sind 
Du hast Recht, wenn man bei der 2a) w schreibt, sollte man hier auch M schreiben.
Mit der f(x) Funktion würde das dann so aussehen?
H<=L2b
f(x) = { <FMw>#z wenn x = w
0 sonst
FM:
Eingabe bin(x)
Starte M mit w
gib bin(x²) aus und halte
Hab im Hefter manche Angaben gefunden, dass man die eigentliche Eingabe von L2b (#z) mit in f(x) geschrieben hat, manchmal steht was festkodiertes wie ne 1 drin und manchmal wieder nichts. Wie schauts denn nun hier bei dem Beispiel aus?
Also gerade „H“ zu wählen fände ich ja schon etwas verwirrend =)
Die Wörter in L2b sind von der Form (oder auch „vom Datentyp“) #z, also eine korrekte Gödelnummer einer det. 1-Band-TM, gefolgt von einem #, gefolgt von einer 0-1-Folge z. Ein Wort sieht also so aus: 11101000010001…111#101
Angenommen, Sie haben nun ein konkretes x=w. Schreiben Sie nun f(x) konkret hin.
Tja, das können Sie nicht, da Sie z nicht haben. Also muß f(x) auch das z konkret angeben!
Richtig wäre also z.B. (nur für den oberen Zweig geschrieben):
f(x) = <FMw>#101 wenn x = w
Ich hatte in der Vorlesung ja mehrfach darauf hingewiesen, daß f(x) im „oberen Zweig“-Fall eine Ausgabe geben muß, die dem Datentyp von (hier) L2b entspricht.
MfG
Rolf Wanka
2 „Gefällt mir“
Vielen Dank für Ihre Antwort!
Der Vollständigheit halber habe ich mal noch den unteren Zweig ergänzt.
H<=L2b
f(x) = { <FM<M>w>#1 wenn x = <M>w
<Mu>#1 sonst
FM:
Eingabe sei x
wenn x = #1
Starte M mit w
gib #1 aus und halte
Mu:
Eingabe sei x
laufe unendlich nach rechts
"=>"
x ∈ H => x =<M>w
=> FM<M>w hält
=> <FM<M>w>#1 ∈ L2b
"<=" ..
=> H <= L2b
Da H unentscheidbar ist es auch L2b.Folglich muss man immer darauf achten, dass die Datentypen in der f(x) Funktion mit denen überein stimmen die auch gefordert sind.
Im sonst-Fall ist die im ursprünglichen Lösungsvorschlag stehende 0 ebenso richtig. Der sonst-Fall will ja gerade nicht, daß man in L2b landet. Wenn man dann absichtlich vom Datentyp abweicht, ist das gerade sichergestellt.
im "Hauptfall!! 
Aus der letzten Klausur ist nicht ganz klar, wie man die Aufgabe 4c loesen soll:
Eine akzeptierende Rechnung ist ja eine Folge von Produktionen/Regeln bzw Konfigurationen, so dass die Folge in einen Endzustand endet.
Sollen wir hier mit der Definition von Ueberfuehrungsfunktionen beweisen?
Sollen ^z Teilwoerter von z, welche immer noch von dem A akzeptiert und in der Sprache L ist, sein?
Wie soll man an diese Aufgabe rangehen? Ein z ∈ L und einen dazugehoerigen Automaten A finden und durch Anwenden von Regeln von L und einer akzeptierenden Rechnung von z die Rechnung so anpassen, dass ^z entsteht?
Das ist imo eine etwas wirre Aufgabe, die rwanka in der Einsicht aber netterweise sehr ausführlich erörterte. An dieser Stelle nochmal danke dafür. 
Es ging darum zu zeigen, dass es, durch die Begrenzung der Zustandsanzahl, nicht möglich ist alle Wörter der Sprache zu akzeptieren, ohne dabei auch Wörter außerhalb (das stimmt in deinem Braindump nicht, es ist \notin ) der Sprache zu akzeptieren. Wichtig dabei sei allerdings den Zuständen keine explizite Bedeutung beizumessen.
Edit
Wo wurde die Aufgabe eroertert?
Für [m]y = 1[/m] erhielte ich m*2 = 18 - 6x \neq 0, x \neq 0[/m]
Ich würde tatsächlich sagen, dass es eher folgendes ist, da laut Definition [m]n[/m] ja auch der erste Parameter zu sein scheint.
[m]f(x, y) = 0, x = 3: (9-9)(y+1) = 0[/m]