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

Neue Frage »

Auf diesen Beitrag antworten »
Nightingale 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
 
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
Nightingale

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.
Auf diesen Beitrag antworten »
Karlito

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
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »