Ja, herzlich willkommen. Sind Sie gut mit Herrn Rauch klargekommen? Insbesondere haben Sie alle

verstanden, wie man einen Automaten minimiert? Das ist wichtig. Da oben wird der Kopf geschüttelt.

Nein, haben Sie nicht. Gut. Also, wie minimiert man einen Automaten? Beispiel ist gewesen. Ja,

das können Sie immer machen. Ja, also es ist jetzt kein großer Notangewinn oder so. Ja,

wenn Sie was nicht verstanden haben, fragen Sie, dann erkläre ich es nochmal. So,

ist das Beispiel da gewesen, wo der Automat an der Tafel minimiert worden ist? Gut. Ich mache

es trotzdem nochmal. Also, wir geben uns einen Automaten, den wir minimieren wollen.

So, der Automat hat fünf Zustände. Q0 bis Q4. So, der Automat verarbeitet Bitstrings,

ja das heißt, das Alphabet besteht aus den Zahlen 0 und 1. Wir haben folgende Übergänge. Das sind

ja deterministische Automaten, das heißt, die haben immer von jedem Zustand aus für jedes

Alphabet-Symbol genau einen Übergang. Also, jeder kriegt einen Pfeil mit einer 0, einen mit einer 1.

Dieser hier hat also eins hier lang, 0 da lang. So, ich mache den Rest einfach mal so hin. Ja, ne, ist das 1?

So, ich hoffe, das ist halbwegs zu erkennen. Ja, also wir haben hier zum Beispiel von Q1 aus,

kommen mit 0 dahin, mit 1 dahin. Von Q2 aus kommen wir mit 1 zu sich selbst. Da machen wir eine

Schleife und mit 0 hier wieder rauf zu Q1. Von Q3 aus kommen wir mit 0 zu Q4 und mit,

teelt der? Ne, den habe ich falsch rumgemalt. Und mit 1 hier unten hin. Und was haben wir noch?

Mit Q4 kommen wir, von Q4 aus kommen wir mit, so jetzt habe ich hier den auch natürlich falsch

rumgemalt, den habe ich ja richtig rumgelesen eigentlich. Also, kommen wir mit 0 hier rauf und

mit 1 da unten hin. So, jetzt haben wir also einen vorschriftsmäßigen deterministischen Automaten.

Minimierung besteht in zwei Schritten, den einen habe ich jetzt weggelassen. Ja, also der erste

Schritt ist der, dass wir den erreichbaren Teil des Automaten bilden. Dass wir also alle Zustände

rauswerfen, zu denen wir vom Anfangszustand, den ich noch nicht markiert habe, dass dieser hier

gar nicht hinkommen. Also, wir können mit ein bisschen testen, sehen, dass wir hier alles erreichen.

Also, den erreichen wir hier über 1, den erreichen wir von da aus über die 0. Dann erreichen wir hier

Q4 über die 0 und hier unten Q2 nochmal über die 1. Also, jeder Zustand hier drin ist erreichbar.

So, und wir minimieren den jetzt, indem wir in unserer Terminologie die größte Bissimulation

auf dem Ding ausrechnen. Und zwar, approximieren wir die von oben. So, das heißt also, wir

identifizieren gewissermaßen Zustände dann, wenn wir können. So, dazu machen wir eine Tabelle.

So, eine Tabelle, natürlich von, gibt es soermaßen letztendlich Paaren von Zuständen,

die wir also identifizieren wollen oder auch nicht. Also, ich schreibe erst die Tabellenbeschriftungen

hin und erkläre dann, warum sie so aussieht. So, was schreiben wir in die Tabelle? Nun,

in die Tabelle schreiben wir Paare von Zuständen. Paar Dinge können wir aber einsparen. Also,

theoretisch müssten das jetzt 5 mal 5 gleich 25 Einträge sein erst mal. Aber, identifizieren

von Zuständen oder nicht identifizieren von Zuständen ist ja symmetrisch. Das heißt also,

die Hälfte der Tabelle kann ich mir durch Diagonales abschneiden schon mal sparen. Und

ich brauche mir natürlich auch nicht die Diagonale anzugucken. Also, ich brauche mir nicht zu

überlegen, ob ich Q0 mit Q0 identifiziere zum Beispiel. Ja, natürlich tue ich das. So,

das heißt, entsprechend weniger Einträge hat jetzt diese Tabelle, die ist jetzt nur noch so

dreieckig wie hier gezeigt. Gut, ob ich jetzt hier von 0 bis 3 gehe und hier von 1 bis 4 oder

umgekehrt ist natürlich egal. So, was fange ich an? Moment, ich muss jetzt noch markieren,

was final ist. Das habe ich natürlich auch noch nicht. Also, Q0 und Q2 sind final. So,

ich kann immer nur finale Zustände untereinander identifizieren oder nicht finale Zustände. Ja,

ich kann die finalen mit einem nicht finalen Zustand zusammenschmeißen, weil die ja offensichtlich

verschiedene Sprachen akzeptieren. Ja, denn ein finaler Zustand akzeptiert das leere Wort und ein

nicht finaler Zustand tut das nicht. So, das heißt, ich gucke jetzt erstmal, was ich hier

streichen muss, weil es einfach verschiedenen Finalitätsstatus hat. Ja, also Q1 und Q0 geht

zum Beispiel schon mal nicht. Also, denn, was habe ich gesagt? Q1 und Q2 und Q0 sind final. Genau,

also die unterscheiden sich schon mal hinsichtlich Finalität. Q2 und Q0, das ist okay,

die sind beide final. Q3 ist nicht final, Q4 ist nicht final. Kann ich alles schon mal streichen.

So, dann, Q2 ist final und Q1 nicht, den kann ich also streichen. Q3 und Q1 sind beide nicht final,