Not logged in. · Lost password · Register

Teacher93
Member since Jan 2012
57 posts
Subject: 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…, 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.
errnosys
Member since Oct 2010
99 posts
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.
Teacher93
Member since Jan 2012
57 posts
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:

1. unerreichbare Knoten streichen
2. alle Paare, die aus Endzustand und Nicht-Endzustand bestehen, streichen
3. für jedes Paar einen Übergang mit jeder Eingabe durchführen; wenn das Ergebnis-Paar schon gestrichen ist, das aktuelle auch streichen
4. Punkt 3 so lange wiederholen, bis sich nichts mehr ändert
5. nicht gestrichene Paare zusammenfassen
Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
622 posts
Quote by Teacher93:
1.  unerreichbare Knoten streichen
Genauer: Vom Startzustand aus aus unerreichbare Knoten streichen.

Quote by Teacher93:
5. nicht gestrichene Paare zusammenfassen
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}.)
quaestor
Christoph Rauch, INF8
Avatar
Member since Sep 2007
98 posts
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.
Metal is like an apple, no one likes the core.
Teacher93
Member since Jan 2012
57 posts
Quote by quaestor:
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?
quaestor
Christoph Rauch, INF8
Avatar
Member since Sep 2007
98 posts
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.
Metal is like an apple, no one likes the core.
Teacher93
Member since Jan 2012
57 posts
Okay, so ergibt das dann auch Sinn. Danke!
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen