Minimierung

[Erendis]

Könnte mir bitte jemand die Minimierung erklären? Hab das nicht ganz durchschaut. Beherrsche derweil nur den ersten Schritt, also die markierung der EZ und NEZ Paare. Weiß sonst nicht wie man die Paare unterscheidet. :(
Wäre sehr lieb
mfg
dex

[maitscha]

Also ich hab mir folgende Schritte überlegt, mit denen man zu der fertigen Unterscheidbarkeitstabelle gelangt:

1. Ich markiere alle End-/Nicht-Endzustände in der Unterscheidbarkeitstabelle mit Epsilon
2. Ich suche mir ein noch leeres Feld (also ein Zustandspaar) aus der Unterscheidbarkeitstabelle
3. Ich suche mir in der Tabelle mit der Übergangsfunktion die beiden Zustände des Zustandspaares heraus.
4. Ich schaue ob es zu diesem Zustandspaar ein anderes Zustandspaar existiert, das bereits als unterscheidbar markiert wurde. Ist dies der Fall, kann ich das aktuelle Zustandspaar auch als unterscheidbar markieren.
5. Ich wiederhole Schritt 2-5 so lange, bis dass die Unterscheidbarkeitstabelle fertig ist und keine Zustände mehr als unterscheidbar vorhanden sind.

[Shades]

hi .. hab da auch eine frage .. ich mach mir diese dreieckstabelle ... usw.. keine Problem, aber wie wirkt sich das ganze auf meinen Graphen aus?

mfg shades

[_logonoff_]

hi .. hab da auch eine frage .. ich mach mir diese dreieckstabelle ... usw.. keine Problem, aber wie wirkt sich das ganze auf meinen Graphen aus?

ganz einfach: die ununterscheidbaren Zustände kannst du samt und sonders durch einen Zustand ersetzen. Wenn du diese Zustandsersetzung zuerst in deiner Übergangsfunktions-Tabelle machst und dir dann aus dieser den minimierten Automaten malst, isses vielleicht eindeutiger.

[gck]

dieser thread behandelt mehr oder weniger diesselben fragen: http://www.informatik-forum.at/~iforum/showthread.php?t=20517