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.
Altklausur WS 2009/10
Ich sitze grade an Aufgabe 2 der Altklausur und komme bei der Reduktion des Komplements des Halteproblems einfach auf keinen grünen Zweig. Mein Problem ist, dass die feste Maschine doch u.a. halten müsste, falls M gestartet mit w nicht hält und die Eingabe von entsprechender Form ist. Wie soll das funktionieren?
Edit: Könnte es sein, dass die TM in L nur für eine der beiden Eingaben halten soll, für die andere aber nicht?
Ich habe folgende Feste Maschine definiert:
FM1:
- Eingabe z
- Halte, wenn z von der Form x’#y’
- Sonste starte M mit w // Wenn x in Kompl(H), kommt die FM1 hier nicht weiter → hält nur auf Eingabe x’#y’, liegt somit in L
- Halte // Wenn x nicht in Kompl(H), kommt die FM1 bis hier → hält für alle Eingaben, liegt somit nicht in L
Edit: Variablen etwas angepasst, weil ungünstig gewählt
Du kannst ja bevor du M mit w startest du Eingabe prüfen (auf die beiden Werte, die du in der Funktion angibst.). Dann hält Mfest für diese beiden Werte, für alle anderen nicht (da M mit w nicht hält).
Wenn M mit w hält, hält Mfest hingegen immer und ist damit nicht in L.
Mfest1:
Eingabe y
y = 0?: Halte
y = 1?: Halte
Starte M mit w
Mfest2:
Eingabe y
y = 0?: Halte
y = 1?: Halte
Endlosschleife
<Mfest1>0#1 falls x=<M>w
f(x) = {
0#1 sonst
x ∉ H:
Fall 1: x = w und M gestartet mit w hält nicht => f(x) = 0#1 und Mfest1 hält nur für die Eingaben 0 und 1 => ∈ L
Fall 2: x ≠ w => f(x) = 0#1 (hält nur für 0 und 1) => ∈ L
x ∈ H => f(x) = 0#1 und M gestartet mit w hält => 0#1 hält für alle Eingaben ∉ L
Mich hat gerade nur der Hinweis in der Aufgabe irritiert, warum steht der denn da? Hat sich erledigt.
@Jase: Aber die Turingmaschinen in L halten ja gerade nicht, wenn die Eingabe von der Form x#y ist. Sondern nur, falls die Eingabe x oder y ist.
@Dalek: Danke, das sieht gut aus. Der springende Punkt der mir gefehlt hat war, dass die TM ja nicht mehr in L ist, falls sie nach der Simulation von M mit w hält.
L = { x#y | M hält nur auf den Eingaben x und y \in {0,1}}
heißt für mich => M gestartet mit {0,1}#{0,1}* hält => M gestartet mit einer Eingabe von der Form x#y hält
Nach Daleks Interpretation wäre L = { x | M hält nur für 2 verschiedene Eingaben aus {0,1}*}
Oder denke ich falsch?!
Ich denke du liegst da falsch. x#y ist lediglich die Sprachsyntax. Ein Element w aus L besteht aus einer Gödelnummer eine TM und einem x#y. Für M muss gelten, dass diese nur mit der Eingabe x und der Eingabe y hält.
Die # vor dem | ist also Sprachsyntax, die angibt, wie ein Element der Sprache aussieht.
Deine Sprache würde ich schreiben als:
L = { x#y | M hält nur mit der Eingabe x#y}
Du hast da 'nen kleinen Denkfehler drin. Die Elemente der Sprache L haben zwar die Form x#y, M selbst hält aber nur für die Eingaben x und y. Die Sprache besteht also aus allen Kombinationen aus Gödelnummer und Eingabe der Form x#y für die die entsprechende Turingmaschine ausschließlich für die Eingabe x und die Eingabe y hält. So verständlich?
Hmm… wenn M nur für x und y hält, wobei die beiden in {0,1}* liegen, müsste M dann nicht für jede Eingabe halten? Weil die Eingaben kommen doch alle aus {0,1}*?
Warum? M muss für zwei konkrete Eingaben aus {0,1}* halten.
Ich glaube ich denke zu Allgemein und will für jede mögliche Eingabe zeigen das es eine Red.fkt. gibt.
Aber wenn das so ist, wird mir so einiges klar 
Soll man eigentlich bei Aufgabe 5a) den rijk Algorithmus anwenden oder vielleicht doch nur die akzeptierte Sprache angeben?
Mit dem rijk Algorithmus würde das Umformen bei 5 Zuständen doch ein wenig lang dauern.
Daher sollte es genuegen, „nur“ die akzeptierte Sprache anzugeben - Rijk kommt ja in der Aufgabe 6 nochmal „richtig“ dran.
-chris
Was käme da bei der 6b) denn raus?
k = 5
L(A) = R_1,1 (R_1,2 ∪ R_1,5) ?
Ich habe hier mal die Indexe um eins verschoben, da nach der Rijk Definition die ich hier habe die Indexe der Zustände bei 1 anfangen.
Ich geh davon aus dass bei der 6b) nach der allgemeinen Definition des reg. Ausdrucks gefragt ist (aka wie bekomm ich mit Rijk den regulaeren Ausdruck)
Und das geht wie folgt:
Wobei n = |Q|.
Kurze Erklaerung: Wir vereinigen alle Ausdruecke, die zu einem Endzustand fuehren (jedem aus F). Diese Ausdruecke lassen sich rekursiv mit den in Teilaufgabe a) gefragten Formeln berechnen.
EDITH spricht: Falls du das gerade auf den NFA A aus Aufgabe 5 beziehst: Hier muesste sein.
Du hast 5 Knoten und dein einziger akz. Endzustand ist q2.
-chris
Thx. Irgendwie ist mir dieser Ausdruck komplett entgangen :-/
Anmerkung, kann es sein, dass diese Vereingungsmenge nur ausreicht, wenn q_1 der einzige Startzustand ist, also S = {q_1} ???
Streng genommen müssen alle i,j berücksicht werden, wobei q_j in F und q_i in S ???
Den Rijk Algorithmus haben wir in der Vorlesung nur fuer DFAs definiert, bei DFAs gibts nur einen Startzustand (sonst waers ein NFA, da epsilon-Uebergaenge zwischen den „Startzustaenden“ - wir haben bisher immer nur einen Zustand zum Startzustand ernannt!).
Die von mir gepostete Formel bezieht sich hier darauf, das q1 der Startzustand ist, das ist korrekt.
Unter der Annahme, dass Rijk auch fuer NFAs funktionniert sollte 
zur Berechnung dennoch ausreichend sein, da „Rijk das schon richten wird (-> epsilon-Uebergaenge zwischen den ‚Startzustaenden‘)“
Aufgabe 3b)
Kann es sein, dass L_2b = { ([ ]) [sup]k[/sup] | k >= 0 } beabsichtigt worden war. Sprich anstelle der Produktion S → [ S ] die Produktion S-> [ ] gemeint gewesen ist.
Weiss gerade nicht, wie ich von den beschriebenen Produktionen zu einer Sprachbeschreibung in Mengenschreibweise kommen soll.
Um die P.E. zu zeigen, möchte ich aber doch so eine Mengenschreibweise haben…
Es gibt ja per Definition des DFA auch nur einen Startzustand.
Anderenfalls, also mit mehr als einen Startzustand, wüßte man ja nicht, wo man anfangen soll, und hätte somit einen nichtdeterministischen FA. Aber dann kann man einen neuen Zustand q’[sub]0[/sub] hinzunehmen, den mit ε-Übergängen an die (nun veraltenden) Startzustände anbinden und q’[sub]0[/sub] als einzigen Startzustand nehmen. Wenn man diesen NFA nun wieder in einen DFA verwandelt, kommt ein DFA mit genau einem Startzustand raus. Also braucht man nie (weder bei DFA noch NFA) mehrere Startzustände.
MfG
Rolf Wanka