Thema: Diverse Reduktionen |
|
Hi Karlito, danke für deine Mühe. Bist du eig. der Einzige der hier in theoretischen Teil des Forum Fragen aufgreift und beantwortet? Wäre schade drum.
Nein ich studiere nicht in Dresden, sondern in NRW.
Hattest du denn schon etwas Gelegenheit mal drüber zu schauen, bzw. soll ich evtl. zum (Wieder-)Einstieg nochmal K<=H oder H<=H0 hier posten?
Beste Grüße
Nightingale
|
|
Thema: Diverse Reduktionen |
|
Hehe, ach kein Problem, jetzt wo du es sagst Fakt es mir sonst auf, dass man das verwechseln könnte - gerade in der Kombi. Es im anderen Thread Reduktionsbeweis genannt zu haben, hatte wohl auch nicht nicht viel gebracht. Hehe und ich dachte mir schon woher du schon weißt, dass du nen anderes Verfahren dazu verwendest.
Wie gesagt, kann man f() direkt angeben sollte es nicht ganz so schwer sein, auch wenn meine Überlegungen etwas knackiger sein könnten. Aber muss man die Reduktionsfunktion verbal beschreiben wird es doch komplizierter und ich unsicherer.
Ich denk mir dann immer, oder war es doch anders herum und verwirre mich selbst. Daher hätte ich gerne etwas mehr Routine darin um sicherer um werden.
Wie gesagt, wäre nett wenn du oder andere mal mit drüber schauen würden. Kann denke nicht schaden das mit mehreren mal anzuschauen.
|
|
Thema: Diverse Reduktionen |
|
Hallo, das Prinzip hinter dem Reduktionsbeweis habe ich soweit verstanden und bei sowie auch nachvollzogen.
Jetzt habe ich mich ein paar Reduktionsaufgaben gewidmet wobei ich die Reduktionsfunktion meist verbal beschreiben musste, einmal aber auch direkt angeben konnte. Beim Beschreiben bin ich noch eher unsicher ob es der richtige Ansatz ist, oder wohl Aussagekräftig genug ist.
Ich denke ich poste einfach erstmal 2 Aufgaben, dann kann man weitersehen.
Zitat: |
Aufgabe 2)
Gegeben sind die Mengen
= { | hält auf Eingabe 1 nicht an },
= { | hält auf allen Eingaben nicht an }.
Zeigen Sie, dass die Menge unentscheidbar ist, indem Sie auf reduzieren.
Meine Lösung:
Zu zeigen:
Konstruiere :
Man kann jedem Wort eine Turingmaschine zuordnen, die wie folgt verbal beschrieben ist...
Ist das Band zu Beginn nicht leer, löscht den Inhalt zunächst.
Auf leerem Band schreibt nun '1' aufs Band und verhält sich dann so wie (also der in kodierten Turingmaschine aus ).
Da sowohl berechenbar, als auch total ist, vermittelt die gewünschte Reduktion.
Überlegung: Bei dem Reduktionsbeweis bettet man ja das bereits bekannte Problem in ein neues ein. Im neuen Problem wird auf allen möglichen 1er-Kombinationen als Eingabe nicht gehalten. Die Eingabe 1 wie im alten Problem ist dort also bereits enthalten. Wenn ich sage, egal was meine aktuelle Eingabe ist, ich verwerfe diese und schreibe lediglich exakt 1 aufs Band und führe dann aus, habe ich das alte ins neue Problem eingebettet. Das alte Problem war schon unentscheidbar, somit wird es das neue Problem erst recht sein.
Passt das zumindest ungefähr so?
|
Wenn ich die beiden Aufgaben geblickt habe, kann ich gerne noch 2-3 weitere Beispiele bearbeiten und reinstellen, falls dort dann jemand nochmal drüber schauen mag.
|
|
Thema: Verständnisfrage: Minimal-Automat, nicht-erreichbarer Zustand, Vollständigkeit |
|
Super, dankeschön. Das ergibt Sinn.
Sorry für die verspätete Antwort, war ein paar Tage weg.
Wie genau binde ich denn die LaTeX-Ausdrücke so schon ein? Ich wollte morgen/nachher nämlich noch einen Thread bzgl. Reduktion auf machen und nicht schon wieder alles als selbst-gekritzelte Screenshots hochladen.
Bist Du in Reduktion auch so fit und kannst mir etwas auf die Sprünge helfen? Prinzip ist klar, bei der Anwendung haperts nochn bissel, hehe.
Egal, bis später erstmal und noch mal besten Dank für die Hilfe.
|
|
Thema: Verständnisfrage: Minimal-Automat, nicht-erreichbarer Zustand, Vollständigkeit |
|
Hallo, ich habe einen gegebenen DEA minimiert, wobei sich eine Verständnisfrage bezüglich eines nicht-erreichbaren Zustands ergab.
Hier erst einmal meine Anwendung der Minimierung, falls sich ein Fehler eingeschlichen haben sollte.
Zitat: |
Der gegebene DEA:
1. Erstelle Minimierungstabelle mit allen Zustandspaaren wie folgt:
2. Markiere alle Zustandspaare (z, z') für die gilt z ElementVon E UND z' NichtElementVon E, wobei E = { z5 }
3. Prüfe für alle Elemente des Alphabets und für alle Zustandspaare ob deren "Nachfolger-Zustandspaar" bereits markiert ist. Wenn ja markiere auch dieses Zustandspaar. Wiederhole diesen Schritt, bis sich keine Änderungen mehr in der Tabelle ergeben.
|
Hier nun der minimierte DEA:
Man sieht das z4 weder Startzustand ist, noch von den anderen Zuständen erreicht werden kann. Durch die Minimierung ist dieser Zustand jedoch nicht weggefallen.
Meine Frage:
Ist das nun der korrekte und vollständige Minimal-Automat, oder könnte man z4 genauso gut wegfallen lassen?
Ist der Automat dann nicht noch minimaler, aber gilt dann nicht mehr als vollständig?
Bei einem Toten Zustand sähe ich ein, dass der gebraucht würde, alleine um aus dem DEA keinen NEA werden zu lassen, aber bei z4 bin ich mir unsicher.
Evtl. kann mich jemand aufklären?
|
|
|