Minimierung deterministischer endlicher Automaten
Вставка
- Опубліковано 14 бер 2019
- Für deterministische endliche Automaten (DEA) können überflüssige Zustände verschmolzen und die Automaten auf diese Weise minimiert werden. Dabei ist der minimale DEA für eine reguläre Sprache eindeutig bestimmt bis auf die Benennung der Zustände.
Sie haben gerade ein Leben gerettet. Tausend dank für die wunderschöne Erklärung
Danke :)
Danke dir, hat mir sehr geholfen. Auch weil ein paar Spezialfälle dabei sind.
Tolle Erklärung, Danke!
Vielen Dank für Ihr tolles Video, sehr gut erklärt, gutes Beispiel.
Vielen lieben Dank! Es hat mit auf die Sprünge geholfen!
Perfekt und sehr detailliert erklärt 👍
Geiler Typ, super erklärt
vielen Dank!!
Endlich kapiert. Mein pensionierter Dozent ist einfach zu unfähig und seine Folie absoluter Müll. Merci dafür!
teilweise hilft einfach eine andere und zweite Erklärung, schön, dass es geholfen hat :)
@@andreas.schaefer Ja das hilft oft. Leider verstehen es die meisten aus der Klasse nicht.
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?
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.
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 😅
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.
@@andreas.schaefer vielen Dank für das tolle Erklärvideo und die schnelle Antwort!
Wer kann das kurz zusammenfassen
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
Wenn die eigene Uni es komplett scheiße erklärt
Danke
Echt so😂