Not logged in. · Lost password · Register

Page:  1  2  3  next 
nenas
Avatar
Member since May 2012
229 posts
Subject: Lösungsversuch Klausur WS13/14
+1 falk
Hi,

zur Vorbereitung versuche ich mich gerade an der Altklausur vom letzten Semester.
Hier meine Ideen, ich bitte um Korrektur, wenn was falsch ist:

1. 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.

2.
a) H = {<M>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.

3.
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.

4.
a) L = {w in {a,b}* | w enthält bb}

b) (gibts ein Programm zum Automaten zeichnen?)

[Image: http://i.imgur.com/At5NuUK.jpg]



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.
Sometimes, I guess there just aren't enough rocks.
This post was edited 4 times, last on 2014-07-18, 14:12 by nenas.
qwert
Member since May 2011
165 posts
+1 nenas
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.
falk
Member since Aug 2013
9 posts
+1 nenas
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-3*x)*(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
This post was edited 4 times, last on 2014-07-20, 17:16 by falk.
Edit reason: Antworten korrigiert und ergänzt.
nenas
Avatar
Member since May 2012
229 posts
Bei der 5 bin ich genauso weit wie du.
Die 6b) ist hier beantwortet
Sometimes, I guess there just aren't enough rocks.
falk
Member since Aug 2013
9 posts
Ich habe die 6 mal noch reingeschrieben.

Gibt es irgendwo Übungsaufgaben mit Lösungen zu sonen µRekursiven Sachen wie bei 5. b)?
nenas
Avatar
Member since May 2012
229 posts
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.
Sometimes, I guess there just aren't enough rocks.
falk
Member since Aug 2013
9 posts
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?
nenas
Avatar
Member since May 2012
229 posts
Ich würd mal behaupten das so was in der Art reicht:

1. Eingabe sei bin(x).
2. Starte M mit w.
3. 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.
Sometimes, I guess there just aren't enough rocks.
This post was edited on 2014-07-20, 11:43 by nenas.
Edit reason: M anstatt H
/dev/null
Member since Mar 2013
83 posts
+1 nenas
Quote by nenas:
2. Starte H mit w.

Wieso wird nicht M mit w gestartet?
nenas
Avatar
Member since May 2012
229 posts
Quote by /dev/null:
Quote by nenas:
2. Starte H mit w.

Wieso wird nicht M mit w gestartet?

Weil Namen Schall und Rauch sind ;)
Du hast Recht, wenn man bei der 2a) <M>w schreibt, sollte man hier auch M schreiben.
Sometimes, I guess there just aren't enough rocks.
falk
Member since Aug 2013
9 posts
Mit der f(x) Funktion würde das dann so aussehen?

H<=L2b

f(x) = { <FM<M>w>#z wenn x = <M>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?
L. F. Ant
Avatar
Member since May 2011
1130 posts
In reply to post #10
Quote by nenas:
Quote by /dev/null:
Quote by nenas:
2. Starte H mit w.

Wieso wird nicht M mit w gestartet?

Weil Namen Schall und Rauch sind ;)
Du hast Recht, wenn man bei der 2a) <M>w schreibt, sollte man hier auch M schreiben.

Also gerade "H" zu wählen fände ich ja schon etwas verwirrend =)
Your argument is irrelephant.
rwanka
Member since Mar 2009
245 posts
In reply to post #11
+2 falk, nenas
Die Wörter in L2b sind von der Form (oder auch "vom Datentyp") <M>#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

Quote by falk:
Mit der f(x) Funktion würde das dann so aussehen?

H<=L2b

f(x) = { <FM<M>w>#z wenn x = <M>w
               0                  sonst              

FM:
  Eingabe bin(x)
  Starte M mit w
  gib bin(x²) aus und halte


Angenommen, Sie haben nun ein konkretes x=<M>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) =  <FM<M>w>#101 wenn x = <M>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
falk
Member since Aug 2013
9 posts
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.
rwanka
Member since Mar 2009
245 posts
Quote by falk:
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

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.

Quote by falk:
Folglich muss man immer darauf achten, dass die Datentypen in der f(x) Funktion mit denen überein stimmen die auch gefordert sind.

im "Hauptfall!!  :-D
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  3  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen