Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 5 von 5 Treffern

Autor

Beitrag

Thema: Diverse Reduktionen

Nightingale

Antworten:	5
Hits:	5.885

22.03.2015 02:26

Forum: Berechenbarkeits- und Komplexitätstheorie

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

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

Nightingale

Antworten:	5
Hits:	5.885

19.03.2015 10:06

Forum: Berechenbarkeits- und Komplexitätstheorie

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. großes Grinsen

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

Nightingale

Antworten:	5
Hits:	5.885

Diverse Reduktionen 19.03.2015 01:46

Forum: Berechenbarkeits- und Komplexitätstheorie

Hallo, das Prinzip hinter dem Reduktionsbeweis habe ich soweit verstanden und bei $[latex]K \leq H[/latex]$ sowie $[latex]H \leq H_0[/latex]$ auch nachvollzogen.

Jetzt habe ich mich ein paar Reduktionsaufgaben gewidmet wobei ich die Reduktionsfunktion [latex]f[/latex]

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

Gegeben ist die Menge

= {

| $[latex]M_{w_2}[/latex]$ hält mindestens bei allen Eingaben, bei denen auch $[latex]M_{w_1}[/latex]$ hält }.

Zeigen Sie durch Reduktion, dass [latex]I[/latex]

unentscheidbar ist. Nutzen Sie dafür die bekanntermaßen unentscheidbare Menge $[latex]H_{\forall}[/latex]$ = { [latex]w[/latex]

| $[latex]M_{w}[/latex]$ hält auf allen Eingaben }.

Meine Lösung:
Zu zeigen: $[latex]H_{\forall}\leq I[/latex]$

$[latex]w \in H_{\forall}[/latex]$
$[latex]\Leftrightarrow\ M_{w}\ \text{haelt auf allen Eingaben}[/latex]$
$[latex]\Leftrightarrow\ M_{w_2}\ \text{haelt mindestens bei allen Eingaben, beim denen} M_{w_1} \text{haelt}[/latex]$
$[latex]\Leftrightarrow\ f(w)\in I[/latex]$

mit [latex]f(w) = w[/latex]

Überlegung: Die Turingmaschine $[latex]M_{w}[/latex]$ aus $[latex]H_{\forall}[/latex]$ hält auf allen Eingaben (was im Grunde irrelevant ist). Verkettet man es mit Trennsymbol # wie es [latex]f(w)[/latex]

tut, sind die Turingmaschinen $[latex]M_{w_1}[/latex]$ und $[latex]M_{w_2}[/latex]$ identisch. $[latex]M_{w_2}[/latex]$ hält also sogar exakt bei den Eingaben, für die auch $[latex]M_{w_1}[/latex]$ hält, was nicht im Konflikt mit der Bedingung in [latex]I[/latex]

steht. Soweit OK und genügt das?

Zitat:

Aufgabe 2)

Gegeben sind die Mengen

= {

| $[latex]M_{w}[/latex]$ hält auf Eingabe 1 nicht an },
$[latex]H_{1^+}[/latex]$ = { [latex]w[/latex]

| $[latex]M_{w}[/latex]$ hält auf allen Eingaben $[latex]x \in \{1\}^+[/latex]$ nicht an }.

Zeigen Sie, dass die Menge $[latex]H_{1^+}[/latex]$ unentscheidbar ist, indem Sie [latex]H_1[/latex]

auf $[latex]H_{1^+}[/latex]$ reduzieren.

Meine Lösung:
Zu zeigen: $[latex]H_1\leq H_{1^+}[/latex]$

$[latex]w \in H_1[/latex]$
$[latex]\Leftrightarrow\ M_{w}\ \text{haelt auf Eingabe 1 nicht an}[/latex]$
$[latex]\Leftrightarrow\ M_{w}\ \text{haelt auf allen Eingaben } x \in \{1\}^+ \text{ nicht an}[/latex]$
$[latex]\Leftrightarrow\ f(w)\in H_{1^+}[/latex]$

Konstruiere [latex]f(w)[/latex]

:

Man kann jedem Wort [latex]w[/latex]

eine Turingmaschine [latex]M[/latex]

zuordnen, die wie folgt verbal beschrieben ist...

Ist das Band zu Beginn nicht leer, löscht [latex]M[/latex]

den Inhalt zunächst.
Auf leerem Band schreibt [latex]M[/latex]

nun '1' aufs Band und verhält sich dann so wie $[latex]M_{w}[/latex]$ (also der in [latex]w[/latex]

kodierten Turingmaschine aus [latex]H_1[/latex]

).

Da

sowohl berechenbar, als auch total ist, vermittelt [latex]f[/latex]

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 $[latex]M_{w} \in H_1[/latex]$ 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

Nightingale

Antworten:	3
Hits:	5.539

18.03.2015 02:28

Forum: Automatentheorie

Super, dankeschön. Das ergibt Sinn. smile

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

Nightingale

Antworten:	3
Hits:	5.539

Verständnisfrage: Minimal-Automat, nicht-erreichbarer Zustand, Vollständigkeit 16.03.2015 01:49

Forum: Automatentheorie

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? smile

Zeige Beiträge 1 bis 5 von 5 Treffern