DEA zu NEA
-
Hey Leute!
Hab mir aus eine Sprache einen DEA gebastelt den ich dann in einen NEA umgewandelt hab. Der DEA wurde dann recht komplex insbesondere die ganzen Zustände (rot umrandet) die sehr verworren so nach unten auf dem Bild gehen. Kann man das irgendwie zusammenfassen bzw. erkennt man hier durch "irgendetwas", dass diese rot umrandeten Zustände eine Eigenschleife auf den Zustand {A,B,D,G} ergeben? So wär der NEA nämlich dann laut Lösung richtig!
-
vip@r schrieb:
Hab mir aus eine Sprache einen DEA gebastelt den ich dann in einen NEA umgewandelt hab.
Bist du sicher, daß du da nicht etwas verwechselt hast?
Ansonsten: Die rot umrandeten Zustände und {A,B,D,G} sind (a) alles akzeptierende Zustände und (b) erreichen keinen Zustand außerhalb dieser Gruppe - von daher kannst du alle zu einem Zustand zusammenfassen (entweder sofort durch scharfes Hinsehen oder durch Minimieren des Automaten).
-
Minimierung eines DEAs geht grundsätzlich mit dem Minimierungsalgorithmus, der sich aus der Äquivalenzrelation von Myhill und Nerode ergibt. Erklärt wird er u.a. hier:
http://www.grundstudium.info/theorie/node57.php
-
Ansonsten: Die rot umrandeten Zustände und {A,B,D,G} sind (a) alles akzeptierende Zustände und (b) erreichen keinen Zustand außerhalb dieser Gruppe - von daher kannst du alle zu einem Zustand zusammenfassen (entweder sofort durch scharfes Hinsehen oder durch Minimieren des Automaten).
Es ist aber doch E und C und F teilweise mit dabei welche nicht im Zustand {A,B,D,G} enthalten sind. Oder Vestehe ich da jetzt was falsch?
-
vip@r schrieb:
Es ist aber doch E und C und F teilweise mit dabei welche nicht im Zustand {A,B,D,G} enthalten sind. Oder Vestehe ich da jetzt was falsch?
Wenn du dir den fertigen Automaten vornimmst, sind diese Mengen nur noch Namen für die Zustände - du kannst sie problemlos umbenenennen in q0 bis q11, ohne daß sich etwas an seiner Arbeitsweise ändert. Und wie gesagt, wenn du den Zusammenhang jetzt noch nicht siehst, dürften die Zustände spätestens bei der Minimierung miteinander verschmelzen.
-
Ich werd dann mal minimieren. Ich hab übrigens jetzt schon verstanden wie du das gemeint hast, dass man das durch scharfes hinsehen erkennt. Von diesen rot umrandeten Zuständen geht keine Transition weg, die einen der Zustände q0 - q5 erreicht. Ich denke mal dass hast du damit gemeint.
