Minimierung eines DEA?
Wie kann ich diesen Automaten minimieren? Ich habe die Tabelle mit dem "Dreieck" gemacht und habe keine Minimierung entdeckt, wegen x0 und x1 Äquivalenz. Die Aufgabe lässt aber Schluss folgern, dass man in doch minimieren kann.
1 Antwort
Die Aufgabe kenne ich! Und sie ist ganz einfach!
Man könnte natürlich hier klassisch mit der Methode vorgehen, pro Eingabefolge zu vergleichen, ob sie immer zu derselben Zustandsklasse akzeptierend oder verwerfend führt.
HIer ist aber ganz easy! Denn wenn man mit einer 0 von S_0 zu S_1 zu einem akzeptierenden Zustand gelangt ist, bleibt man in den akzeptierenden Zuständen, weil egal ob 1 oder 0, die akzeptierenden Zustände verweisen immer nur auf akzeptierende Zustände. Damit kann man alle akzeptierende Zustände zusammenfassen, man hat also nur noch S_0, der mit einer 1 auf sich verweist und mit 0 auf S_1, sowie S_1, der mit 0 und 1 auf sich verweist.
Also L(R)= 1*0(1|0)* bzw. L(G) = S -> 1S | 0A und A-> 1A | 0A | eps.
Ansonsten, wenn es nicht so einfach wäre, wirklich pro Zustand vergleichen, Beispiel hier
https://www.youtube.com/watch?v=2FNTDtabQz4
oder per Myhill-Nerode-Relation.
schreibst Du Klausur März :-)?
Ich gehe wie folgt vor: Ich mache eine Tabelle, sowohl horizontal als auch vertikal die Zustände. Wenn ein Zustände final akzeptierend ist, der andere nicht, dann unterscheiden sie sich. Also in der Tabelle bei Zustand a und Zustand b ein x für sich unterscheidend eintragen, so alle Zustandspaare durch.
Als nächsten prüfen wir, ob wir mit derselben Eingabe (immer ein Zeichen, aber für alle Möglichkeiten) von Zustand c und Zustand d in ein sich unterscheidendes Zustandspaar, z.B. hier in Zustandspaar a und b kommen können. Denn dann gäbe es eine Eingabe, welche ein Zustandspaar in ein sich unterscheidendes Unterschiedspaar führt. Dann können die Zustände nicht äquivalent sein.
Und diese (Halb)Tabelle wird durchgegangen, bis man irgendwann keine x mehr einträgt, dann hat man ein volles Bild: Alle freien Felder markieren Paare, die äquivalent sind.
Ich hab mir deine Antwort durch gelesen und verstehe den mittleren Teil nicht so richtig. Ich schreib mal so wie ich es bis jetzt verstanden habe.
S0 bei 0 zu S0
S0 bei 1 zu S1
S1 bei 0 zu S0
S1 bei 1 zu S1
Beide Zustände sind keine Endzustände (ich weiss unlogisch)
Ersten Test bestanden
S0 zeigt bei 0 auf S0 ,genau wie S1 auch
Zweiter Test bestanden
S0 zeigt bei 1 auf S1, genau wie S1 auch
Dritter Test Bestanden
Folgerung Äquivalent und lässt sich minimieren.
Oder ist bei dir Test 2 und Test 3 in einem Test zusammen gefasst? Ist doch eigentlich egal, oder?
Wenn ich das jetzt aber mit der Aufgabe von Oben eine Zustandsübergangstabelle mache stelle ich fest das nie ein Zustand äquivalent ist.
Der erste Schritt ist die Unterscheidung zwischen final akzeptierenden Zuständen und den übrigen. Deswegen unterscheiden wir S_0 und S_1.
Hätten wir weitere Zustände, z.B. S_2 und S_3 und würde bspw. S_2 bei 0 auf S_0 gehen und bei 1 auf S_1, während S_3 bei 1 und bei 0 auf S_0 geht, dann unterscheiden sich auf S_2 und S_3, weil wir einer Eingabe von 1 die Zustände S_2 und S_3 in divergierend ein divergierendes Zustandspaar übergeht, nämlich in das Paar (S_0, S_1). Warum S_0, S_1 divergieren, siehe Absatz 1. Also ist auch S_2 und S_3 ein divergierendes Zustandspaar.
Anderes Beispiel: S_2 geht bei 0 auf S_1, bei 1 auf S_0. Ebenso geht S_3 bei 0 auf S_1, bei 1 auf S_0. Damit haben S_2 und S_3 identisch in S_0, S_1, es ist also egal, ob man von S_2 oder S_3 weitermacht, sowohl bei einer 1 als auch bei einer 0 geht es die denselben Zustandsart.
Soweit klar? (das sind allerdings nur die ersten zwei Schritte, den Rest, wenn soweit klar).
Ja das habe ich verstanden, wie gesagt ich kann das eigentlich auch, nur nicht bei dieser Aufgabe.
Ich schau mir das Video bestimmt schon zum 5mal an und werde nicht wirklich schlauer draus wie dieser Herr es macht. Ich hab das so gelernt: 1. Check Endzustand vergleich 2. Check gehen nach Eingabe x,y die Übergänge zu den Selben Zuständen. Wenn ich diese Vorgehensweise benutze für die Aufgabe, komme ich auf den Schluss das keine Minimierung möglich ist.