Minimierung deterministischer endlicher Automaten
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.
Пікірлер: 22
Sehr anschauliche und gut verständliche Erklärung. Vielen Dank
Sie haben gerade ein Leben gerettet. Tausend dank für die wunderschöne Erklärung
@andreas.schaefer
11 ай бұрын
Danke :)
Danke dir, hat mir sehr geholfen. Auch weil ein paar Spezialfälle dabei sind.
Vielen Dank für Ihr tolles Video, sehr gut erklärt, gutes Beispiel.
Vielen lieben Dank! Es hat mit auf die Sprünge geholfen!
Tolle Erklärung, Danke!
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!
@andreas.schaefer
2 жыл бұрын
teilweise hilft einfach eine andere und zweite Erklärung, schön, dass es geholfen hat :)
@zarlorin3728
2 жыл бұрын
@@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?
@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.
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
11 ай бұрын
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
11 ай бұрын
@@andreas.schaefer vielen Dank für das tolle Erklärvideo und die schnelle Antwort!
Wer kann das kurz zusammenfassen
@andreas.schaefer
11 ай бұрын
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
@zarlorin3728
2 жыл бұрын
Echt so😂