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 2011/2012
Aufgabenteil 4 Automaten: Zeigen Sie, dass AB und AC nicht äquivalent sind!
- Ist mit z.B. AB {A, B} gemeint?
- Wenn ja, dann komm ich immer nur drauf, dass die beiden äquivalent sind…wie genau mach ichs richtig?
Falls 1. damit gemeint ist (weiß es auch nicht …), dann könntest du einen “Beweis” angeben. Für A,B z.B. 0, da B mit einer 0 im Endzustand D landet, A aber in B, wobei wiederrum B und D nicht gleich sein können wegen epsilon. Quasi einen Teil des NEQ Algo hinschreiben …
sollen wir da etwa jeweils A und B und dann A und C miteinander vergleichen?
ich dachte vielmehr, die elemente {A,B} und {A,C} aus der potenzmenge miteinander…
Ist nun mal ein Braindump => Das weiß nur einer der mitgeschrieben hat oder der Ersteller der Klausur.
1 Like
Es war nach Zeugen = „Eingabewörte“ für (Nicht-) Äquivalenz gesucht.
@Otis: Es sollte A mit B unc A mit C verglichen werden.
Ich habe es so gemacht, und es gab entsprechend Punkte…
Danke, das hilft!
Ich haette mal ne Frage zu der Aufgabe 6.
Wie genau wuerdet ihr den letzten Aufgabenteil beantworten ( Angenommen P = NP, zeigen Sie, dass SUMMIERT dann NP-vollstaendig ist)?
Ich haette versucht das mit dem Lemma 2.12 zu begruenden.
Habt ihr noch andere Vorschlaege?
Wenn P=NP kannst du innerhalb der Reduktion dein NP hartes Problem lösen. Siehe Aufgabe 38 aus den Hausaufgaben.
Stimmt, die Aufgabe hatte ich total vergessen. Danke 
Bei der Aufgabe 4 Minimierung von A2, wollte ich mal Fragen, ob man den Zustand E, nicht auch weglassen kann im minimierten Graph. Weil aus E kann ich eh nicht mehr rauskommen und E ist ja kein Endzustand. Oder muss ich E trotzdem mit hinschreiben, damit ich von jedem Zustand aus für 0 und 1 eine Kante hab. Andererseit ist doch der Minimalautomat so, dass es keinen anderen AUtomaten gibt der die gleiche Sprache akzeptiert und weniger Zustände hat, aber wenn ich den Zustand E weglass hab ich doch immer noch einen Automaten, der die selbe Sprache akzeptiert…
Wie macht ihr das mit solchen Zuständen?
Das war in der Vorlesung unklar.
Um einen Minimalautomaten zu erreichen müssen in der Tat auch noch tote Zustände entfernt werden, zur Minimierung zählt das glaube ich aber nach Vorlesung nicht.
Ein Kommentar von rwanka wäre hier interessant ;).
Aufgabe 3 c)
Hab mir folgende Lösung zur 3 c) überlegt, kann man das so machen oder habt ihr da was anders gemacht?
Zeigen Sie, dass L = { z0^|z| | z ∈ {0,1}* } die reg. PE. nicht hat.
Sei p ∈ N bel., aber fest. Setze x := a0^|a| mit a ∈ {0,1}*
|x| = |a0^|a|| = 2*|a| ≥ p
Sei u,v,w bel., aber fest und uvw=x
i) |uv| ≤ 2*|a|
ii) |v| ≥ 1
iii) Setze i := 2
Fall 1 : u = ɛ => |v| ≤ 2*|a|
Fall 1.1: v = a => w = 0^|a| => aa0^|a| ∉ L
Fall 1.2: v = a0^|a| => w = ɛ => (a0^|a|)^2 ∉ L
Fall 2: u = a => v = 0^|a| => w = ɛ => a(0^|a|)^2 ∉ L
Darf man fuer p eigentlich einen festen Wert nehmen?
Natuerlich muss der Wert dann fuer jede beliebe Groesse von z gelten.
So habe ich das naemlich gemacht…
Oder muss ich p allgemein halten?
Weil, wenn ich ich p einen Wert zuweise und dieser aber immer fuer die reg. PE passt, dann sollte das doch erlaubt sein oder?
Wenn du zeigen willst, dass eine Sprache die reguläre Pumpeigenschaft besitzt reicht ein festes p, ja. Ein allgemeines p brauchst du eben, wenn du das Gegenteil zeigen willst, also dass eine Sprache die reguläre Pumpeigenschaft nicht besitzt.
Also ich würde es in etwa so lösen:
Sei p beliebig aber fest. Setze z=1^p 0^p ∈ L, |z| ≥ p.
Sei u,v,w beliebig aber fest:
Aus: |uv| ≤ p folgt, dass u und v nur 1en enthalten
Aus: v ≠ ε folgt, dass v mindestens eine 1 enthält.
Setze i = 0: Da v mindestens eine 1 enthält wird diese weggepumpt. Die Anzahl der 0en passt danach nicht mehr zur Anzahl der vorangehenden Zeichen, also ist z=uv^i w ∉ L => L hat reg. PE nicht.
Vom Gedanken her viel einfacher als meine Lösung und gefällt mir besser.
Ich habe die „toten“ Zustände bisher immer dabei gelassen. Weiß einer mehr?
Tote Zustände könnten vorher erkannt und gelöscht werden. Hinterher können Sie sagen: Diese Zustände hier tragen nichts zur Sprache bei und könnten auch weggelassen werden. Allerdings ist δ dann nicht total und man braucht die (übliche) Konvention, daß man dann verwerfend abbricht. Also: dalassen und einen Hinweis. Zum Glück lesen echte Menschen die Klausur und keine TMs. 
MfG
Rolf Wanka
Das sehe ich anders
Vom Einschränken der Definitionsmenge bekommt eine Funktion sicher keine Definitionslücken.