|
  |
 Verständnisfrage: Minimal-Automat, nicht-erreichbarer Zustand, Vollständigkeit |
Nightingale
Grünschnabel
Dabei seit: 13.03.2015
Beiträge: 5
 |
|
| 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? 
Nightingale hat diese Bilder (verkleinerte Versionen) angehängt:
  
 
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Nightingale: 16.03.2015 01:50.
|
|
16.03.2015 01:49 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Die Minimierung ist bis dahin korrekt (bin mit anderem Verfahren auf das gleiche Ergebnis gekommen). ![[latex]z_4[/latex]](http://www.matheboard.de/latex2png/latex2png.php?z_4) 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, muss noch weg.
Gruß,
Karlito
|
|
|
16.03.2015 09:28 |
|
|
Nightingale
Grünschnabel
Dabei seit: 13.03.2015
Beiträge: 5
|
|
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.
|
|
|
18.03.2015 02:28 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
18.03.2015 12:48 |
|
|
|
|
|
|
|
|
