Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Automaten-Minimierung
Hat da jemand eine Ahnung wie die geht? Wir haben das zwar mal in der Übung gemacht, aber irgendwie kann ich mein Script nicht mehr “decodieren”, weil ich da leider nicht so sauber mitgeschrieben hab…
Ich dachte auch immer, das sei Schnuppe, aber die Aufgabe kommt auch einmal in einer Klausur dran ;-(
hätte ich auch gerne gewusst
also wir haben in der Übung dazu den Algorithmus von Aufenkamp und Hohn besprochen… da der aber doch eher umfangreich is und ich aber leider keinen Scanner besitze wäre es kewl wenn jemand aus meiner Übung den mal ins Netz stellen könnte?!
Ansonste schaut halt mal in der Literatur nach… der is ziemlich einfach aber man muss es halt mal gesehen haben…
btw@Robert: Wer is das chick neben dir auf dem Bild?! 
das wollte ich auch schon mal fragen lol.
Jedenfalls sauber abgetrennt…
Kommt mal wieder runter, das ist nur meine Schwester… 
Oder steht wer von euch auf 15 Jährige?
das ist doch die scheiße mit den äquivalenzklassen, oder?
wenn, das ist das doch nur anwenden von schema F, aber irgentwie besonders behandelt haben wir das nicht…
naja… is doch schön wenn auch mal was einfach ist. Und dieser Algorithmus is eindeutig dafür gedacht Automaten zu minimieren… und das war Roberts Frage.
kann mir dann vielleicht doch jemand diese äquivalenzklassen-aktion erklären? wir haben das heute mal ausprobiert, sind aber zu keinem (sinnvollen) ergebnis gekommen. ich kann mich net so recht dran erinnern und unsere übungs-aufzeichnungen sind eher mager dokumentiert…
gibt’s da nicht irgendwelche literatur (am besten online/digital) wo das nochmal erklärt ist?
Falls jemand das Glück hat und wie ich nicht mehr weiß, wie das mit den Äquivalenzklassen geht, der findet auf folgender Seite nochmal Erklärung:
Algorithmus von Haufenkamp und Hohn
Am besten sich mal das Beispiel anschaun, das ist da recht schön erklärt und sich dann mal am BCD-Automaten aus der Klausur vom 13.10.1998 versuchen.
Gruß
Void
thx fuer den post, allerdings muss ich sagen, diese seite hat mich erstmal komplett durcheinander gebracht. nachdem ich jetzt aber noch mit meinen uebungsmitschriften (soweit ich sie entziffern konnte) gearbeitet habe, bin ich glaube ich auch auf den algorithmus gekommen.
da hab ich mich jetzt mal dran versucht, kann es sein, dass sich bloss die zustaende 4 & 9 und 7 & 10 zusammenfassen lassen?
Ich erhalte nach einigem Gewurschtel folgende Äquvivalenzklassen:
{1}, {2,5}, {3,6,8}, {4, 7, 9, 10}
Bin mir allerdings nicht sicher, ob das richtig ist. Vielleicht mach ich’s nochmal.
Oder hat vielleicht jemand anders zufällig seine Lösung dazu rumliegen?
Gruß
Void
also wenn ihr von dem BCD-code-erkennungs-müll da redet, würd ich einfach mal behaupten, dass man die zustände 2,3,4 und 6,7 jeweils zusammenfassen kann. also das ist doch das ziel der aktion, oder? dass ich zustände zusammenfasse, die den selben effekt haben (gleiches ziel der 0- und 1-pfeile). den algo muss ich mir mal genauer anschauen, mal sehen, ob ich’s kapier…
also, kurz mal meine loesung:
nach 1. schritt:
a1=1
a2=2,3,4,9
a3=5
a4=6,7,10
a5=8
nach 2. schritt:
b1=1
b2=2,3
b3=4,9
b4=5
b5=6
b6=7,10
b7=8
nach 3. schritt:
c1=1
c2=2
c3=3
c4=4,9
c5=5
c6=6
c7=7,10
c8=8
also hat man insgesamt nur zwei zustaende eingespart und einen haufen (!) arbeit gehabt … tolle sache.
das kann imho schon deshalb nicht stimmen, wenn du die 2 und die 5 betrachtest: die 2 reagiert auf beide eingaben mit einer 1-ausgabe und die 5 auf die 1 mit einer 0-ausgabe, auf eine 0 mit einer x-ausgabe. und ausserdem habe die dann noch ganz unterschiedliche folgezustaende. so aehnlich sieht bei mir der 1. schritt aus (s. o.).
stimmt leider nicht ganz, ausserdem wuerde bei der 2,3,4-liste dann noch die 9 fehlen und bei der 6,7-klasse muesste dann noch die 10 dazu.
das ist nur der 1. schritt, das ist auch dein problem bei obiger loesung von dir. du musst ausserdem noch die folgezustaende beachten - es kann zwar sein, dass 2 zustaende gleich auf die 1. eingabe reagieren, aber nicht mehr gleich auf die 2. oder 3. eingabe. und bei diesem programm werden ja letztendlich 4 ziffern hintereinander eingegeben … trotzdem hast du recht, dieser automat ist echt ein muell!
Ja, ich hab mir schon gedacht, dass da der Wurm drinsteckt und die 2 und die 5 nicht ganz in eine Klasse passen, aber ich hatte dann auch keine Lust mehr, zu überprüfen, wo genau ich gemurkst hab. :lachen:
hm was bedeutet das x? kann ich da die ausgabe freiwählen?
Drager
k.a. (*)
aber ich hab den algo von der angegebenen URL jetzt eigentlich soweit kapiert… es muss einem ja nur mal gesagt werden, welche zahlen ich wohin schreiben soll und wie damit weiter zu rechnen ist 
das mitgelieferte beispiel hat auch super funktioniert, aber die 1998-aufgabe irgendwie gar nicht. kann vielleicht einer von den checkern die tabellen posten?
*) das x hab ich als eigene, neue ausgabe genommen und das schaut dann ganz gut aus eigentlich…