Minimierung deterministischer endlicher Automaten

[@tizaf]

Sie haben gerade ein Leben gerettet. Tausend dank für die wunderschöne Erklärung

[@andreas.schaefer]

Danke :)

[@Ben-up4lj]

Danke dir, hat mir sehr geholfen. Auch weil ein paar Spezialfälle dabei sind.

[@qpxxl]

Sehr anschauliche und gut verständliche Erklärung. Vielen Dank

[@tulamhosoduhocduc]

Vielen Dank für Ihr tolles Video, sehr gut erklärt, gutes Beispiel.

[@davidwagner6973]

Vielen lieben Dank! Es hat mit auf die Sprünge geholfen!

[@JohnClasher]

Perfekt und sehr detailliert erklärt 👍

[@sempribo]

Tolle Erklärung, Danke!

[@märchenonkel-v7y]

Geiler Typ, super erklärt

[@pyuc]

12:23 ich verstehe nicht, warum man für den die Zustände q0 und q4 die Gesamttabelle am Ende nochmal durchgehen muss. Wir haben diese Zustände doch bereits getestet und sonst ja nichts weiter am Automaten geändert. Warum muss man also am Ende das nochmal kontrollieren?

[@andreas.schaefer]

In dem Schritt vorher haben wir Markierungen zugefügt. Es könnten also jetzt neu die Nachfolger von q0 und q4 bei Eingabe a oder b jetzt markiert sein. Wenn das so wäre würde jetzt auch q0,q4 markiert werden. In diesem Fall kann das nicht sein, weil man mit a in beiden Fällen zu q2 und mit b zu q3 kommt. Aber im Allgemeinen muss man immer alle unmarkierten durchgehen, bis sich einmal nichts mehr geändert hat. Damit das klarer wird, probieren Sie mal den Automaten q0 -a-> q1 -a-> q2 -a-> q3 -a-> (q4) wobei q4 der einzige Endzustand ist und einen a-Übergang zu sich selbst hat. Da wird zuerst q3,q4 markiert, dann wird die Tabelle durchgegangen und dann q2,q3 markiert, dann erneut durchgegangen und q1,q2 markiert und dann wieder durchgegangen und q0,q1 markiert.

[@pyuc]

@@andreas.schaefer Danke für die Antwort. Ich habe es verstanden. Wie bereits öfter erwähnt wurde das Thema verständlich erklärt. Vielen Dank für das Video

[@zarlorin3728]

Endlich kapiert. Mein pensionierter Dozent ist einfach zu unfähig und seine Folie absoluter Müll. Merci dafür!

[@andreas.schaefer]

teilweise hilft einfach eine andere und zweite Erklärung, schön, dass es geholfen hat :)

[@zarlorin3728]

@@andreas.schaefer Ja das hilft oft. Leider verstehen es die meisten aus der Klasse nicht.

[@soerenkierkegaard2968]

was passiert wenn man für ein Tupel von Zuständen die Folgezustände für eine Eingabe überprüfen will ( zB. a) aber nur einer der Folgezustände eine Verbindung hat, die über a geht? Einer der beiden Folgezustände hätte dann einfach ein "leeres" Feld? Wie kann ich mit so etwas umgehen?

[@andreas.schaefer]

Das ist eine gute Frage. Es kann nicht passieren, weil die Automaten DEAs sind also in jedem Zustand für jedes Symbol genau einen Übergang haben.

[@300selena]

vielen Dank!!

[@ashar8192]

Kann man die Tabelle für jeden DFA, wie im Video, aufstellen, so dass die rechte obere Hälfte nicht überprüft werden muss? Unser Prof und die Assistenten halten sich nicht an eine Konvention und andere scheinen auch die Tabelle immer anders aufzustellen 😅

[@andreas.schaefer]

Ja, wenn (q1,q2) verschmolzen oder nicht verschmolzen werden sollen, gilt das natürlich auch für (q2,q1), wir brauchen also jedes Paar nur einmal. Und wir müssen einen Zustand nicht mit sich selbst prüfen, also fallen (q1,q1) Paare auch weg. Es gibt aber keine wirkliche Konvention wie man die Tabelle aufschreibt. Ich mache es wie Uwe Schöning in seinem Buch.

[@ashar8192]

@@andreas.schaefer vielen Dank für das tolle Erklärvideo und die schnelle Antwort!

[@TENGENTOPPAGL]

Wenn die eigene Uni es komplett scheiße erklärt Danke

[@zarlorin3728]

Echt so😂

[@Pablo-np6lo]

Wer kann das kurz zusammenfassen

[@andreas.schaefer]

Markiert werden die nicht(!) zusammenzufassenden Zustände. Zuerst alle Paare markieren wo Endzustand und Nichtendzustand ist. Dann alle Paare durchgehen mit alle Buchstaben und gucken zu welchem Paar man kommt. Wenn Zielpaar schon markiert ist, Ausgangspaar auch markieren. Solange machen, bis sich nichts ändert