Informatiker Board | Druckvorschau: Verständnisfrage: Minimal-Automat, nicht-erreichbarer Zustand, Vollständigkeit

Geschrieben von Nightingale am 16.03.2015 um 01:49:

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

Geschrieben von Karlito am 16.03.2015 um 09:28:

Die Minimierung ist bis dahin korrekt (bin mit anderem Verfahren auf das gleiche Ergebnis gekommen). [latex]z_4[/latex]

konnte schon im Ursprungsautomaten nicht erreicht werden. Du hättest es also da schon weg fallen lassen können und sollen, da nicht erreichbare Zustände für den Automaten keine Bedeutung haben. (Erspart dann auch ein wenig Arbeit)
Die Minimierung fasst nur äquivalente Zustände zusammen. Es fallen also eigentlich keine Zustände weg, sie werden nur zu einem neuen Zustand zusammengefasst, der sich äquivalent zu der zusammengefassten Zustandsmenge verhält.

Edit: Fazit: ja, [latex]z_4[/latex]

muss noch weg.

Gruß,

Karlito

Geschrieben von Nightingale am 18.03.2015 um 02:28:

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.

Geschrieben von Karlito am 18.03.2015 um 12:48:

Hallo Nightingale,

ich denke, dass ich relativ fit bin, wende aber ein anderes Verfahren an. Du kannst deine Fragen deshalb gerne hier stellen.

Latex bindet man hier ein, indem man den Latex-Code in [latex] [/latex] einbettet.

Gruß,

Karlito