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.
Minimierung eines DFA
Ich komme derzeit mit dem DFA-Minimierungsalgorithmus nicht zurecht.
Nehmen wir mal den Graphen aus https://fsi.cs.fau.de/dw/_media/pruefungen/bachelor/thprog_theorems.pdf, Seite 10.
Den Zustand h zu entfernen ist klar. Der ist ja nicht erreichbar.
Danach werden alle Paare aus dem Endzustand d und den anderen Knoten überprüft, ob sie ohne Zustandsübergang gleich sind… ist das bei einem DFA nicht sinnlos? Es gibt ja keine ε-Übergänge.
Anschließend werden alle Paare mit Eingabe 1 ausgewertet. Wenn eine im Ergebnis-Paar schon eine 0 drin steht kommt ne 1 rein, sonst nichts, oder? Beim Paar a-f kommen beide auf c, kann ich die damit schon auf × setzen? Weil mit Eingabe 0 landen sie wo anders. Oder kommt das erst im nächsten Schritt?
Am Ende kann ich a-f und b-g zusammenfassen. Oder muss ich noch was überprüfen?
Gibt es dazu auch irgendwo eine geschriebene Anleitung? Das Dokument oben ist ja nicht offiziell und online findet man auf jeder Seite eine andere Vorgehensweise.
Algorithmus 6.19 im Skript auf der Vorlesungsseite beschreibt die Vorgehensweise, bzw. der Fließtext danach erklärt die Tabelle.
Zu deinem konkreten Beispiel: Die Paare (d,x) mit x irgendein Knoten werden für das leere Wort überprüft, d.h. alle paare aus nicht-finalen und finalen Zuständen werden getrennt. Kenntlich gemacht wird das durch die 0 in der Tabelle.
Wenn ich dich richtig verstehe, dann kommt deine Verwirrung daher, das es zwei unterscheidliche Arten von “Zahlen” gibt, die du verwechselst: Zum einen gibt es da die zwei Zeichen des Eingabealphabetes, und zum anderen gibt es die Länge der betrachteten Eingaben. D.h. es ist bestimmt Hilfreich zu überlegen, was sich ändern würde, wenn das Eingabealphabet {o,i} wäre statt {0,1}.
Beim Paar a-f kommen zwar beide bei einer Eingabe 1 (d.h. “i”) auf c, allerdings auf unterschiedliche Zustände für die Eingabe 0 (d.h. “o”). Deshalb kannst du a-f nicht direkt auf x setzen.
Danke für die Antwort! Ich hab mir die Vorlesungsaufzeichnung nochmal angeschaut und da schreibt er in die Tabelle überhaupt keine Zahlen. Das finde ich viel einfacher, da mich die Zahlen nur verwirren.
Das funktioniert dann etwa so:
- unerreichbare Knoten streichen
- alle Paare, die aus Endzustand und Nicht-Endzustand bestehen, streichen
- für jedes Paar einen Übergang mit jeder Eingabe durchführen; wenn das Ergebnis-Paar schon gestrichen ist, das aktuelle auch streichen
- Punkt 3 so lange wiederholen, bis sich nichts mehr ändert
- nicht gestrichene Paare zusammenfassen
Genauer: Vom Startzustand aus aus unerreichbare Knoten streichen.
Angenommen es bleiben folgende Paare übrig: (D, F) (A, B), (C, D), (B, E), (C, F), (A, E)
Dann fässt du zusammen:
- {A, B, E}
- {C, D, F}
(Das sind die mehrelementigen Äquivalenzklassen der Menge der Knoten unter der Relation, die durch die Paare gegeben ist. Die einelementigen Klassen sind dann alle nicht zusammfassbaren Knoten, etwa {X}, {Y}, {Z}.)
Die Zahlen in der Tabelle können in der Klausur eine Hilfe sein. Denn füllt ihr die Tabelle mit x-en, ist für die Korrektoren nicht nachvollziehbar, bis zu welcher Iteration der Algorithmus vielleicht noch korrekt ausgeführt wurde, falls irgendwo ein Fehler passiert. Also einfach nach jeder Wiederholung von Punkt 3 in obigem Post die Zahl erhöhen.
Heißt das wirklich bei jedem Durchlauf einfach eine höhere Zahl rein schreiben, oder wenn im Ergebnis-Paar schon eine 2 drin steht eine 3 rein schreiben?
Letzteres. Dann bedeutet die Zahl die Länge eines Wortes, das die beiden Zustände unterscheidet. Zudem ist die erste Möglichkeit nicht unabhängig von der Reihenfolge, in der man die Felder abklappert, es sei denn, man ignoriert in jedem Durchlauf Felder, die die Zahl des aktuellen Durchlaufs enthalten; dann sind die beiden Möglichkeiten äquivalent.
Okay, so ergibt das dann auch Sinn. Danke!