DFA minimieren

Auch wenn es mindestens die Hälfte meiner Leserschaft nicht wirklich interessieren wird, zeige ich hier mal wie man einen DFA per Hand (auch) minimieren kann. Das ist nämlich eigentlich recht einfach, solange der DFA simpel genug ist, wird aber oft genug kompliziert erklärt.
Nehmen wir folgenden DFA als zu minimierenden:
Ein unnötig großer dfa
Minimieren kann nur funktionieren, wenn man überflüssige Zustände entfernt bzw. zusammenfasst. Am Anfang haben wir kein weiteres Unterscheidungsmerkmal als die Frage, ob die Zustände final sind (im Bild oben dargestellt durch die Doppelkreise) oder nicht. Grafisch betrachtet sieht das dann so aus (die Linien stellen die Übergänge dar, a ist blau, b braun, ab türkis)
grafische Methode zum Minimieren
Der Doppelpunkt markiert das nächste Unterscheidungskriterium: Zustand 1 und 2 gehen über a bzw. b in die linke Gruppe, Zustand 5 geht jeweils in sich selbst, also in die rechte Gruppe: Hier kann innerhalb der Gruppe "125" nochmal unterschieden werden zwischen "12" (gehen beide in die linke Gruppe) und "5" (geht in die rechte Gruppe).
Nun sieht der nächste Schritt so aus:
Grafische Methode zum Minimieren
Da 3 und 4 nun auf eine andere Gruppe als 0 zeigen, kann jetzt auch in der linken Gruppe unterschieden werden.
Führt man das Verfahren nun nochmal aus, zeigt jedes Gruppenmitglied auf die gleiche Gruppe, ein weiteres Unterscheiden ist also nicht möglich.
Der fertig minimiert DFA sieht also wie folgt aus:
ein minimierter dfa

PS: Die DFAs wurden mit dem Automaton Simulator gezeichnet.
Puppetmaster87 (Gast) - 17. Dez, 14:45

danke für die erklärung. ist auf jeden fall verständlicher, als alles, was ich bisher so gelesen hab.

leider hab ich gerade ein beispiel bei dem die pfeile meistens in 2 verschiedene gruppen zeigen.

kannst du mir da weiterhelfen?

onli - 17. Dez, 15:47

Wenn die Pfeile a b in zwei verschiedene Gruppen zeigen, ist das an sich kein Problem. Auch dann sollte es Gruppen von Zuständen geben, die zusammen in die zwei verschiedenen Gruppen zeigen. Die kann man dann einfach auch zusammenfassen.
Aufpassen muss man dann nur besonders darauf, dass sie nicht nur in die gleichen Gruppen zeigen, sondern dass auch jeweils das a in die gleiche Gruppe zeigen muss.
Zeigt 1 über a in 3 4, 2 aber über b in 3 4, dann kannst du 1 und 2 nicht zusammenfassen. Zeigt aber bei 1 und 2 a in 3 4 und das b zeigt auch jeweils in die gleiche Gruppe, dann kannst du die zusammenfassen.
Mark (Gast) - 4. Apr, 20:34

Endlich mal eine einfache Erklärung im Internet. Vielen Dank! :)

onli - 5. Apr, 00:08

Freut mich das sie hilft :)

Trackback URL:
http://onli.twoday.net/stories/4592568/modTrackback

Aktuelle Beiträge

Freut mich das sie hilft...
Freut mich das sie hilft :)
onli - 5. Apr, 00:08
Endlich mal eine einfache...
Endlich mal eine einfache Erklärung im Internet....
Mark (Gast) - 4. Apr, 20:34
Wenn die Pfeile a b in...
Wenn die Pfeile a b in zwei verschiedene Gruppen zeigen,...
onli - 17. Dez, 15:47
danke für die erklärung....
danke für die erklärung. ist auf jeden fall...
Puppetmaster87 (Gast) - 17. Dez, 14:45
wird gemacht
Danke. Ich werde Chrome weiterverfolgen. Nächstes...
onli - 8. Sep, 09:27

Suche

 

Status

Online seit 3484 Tagen
Zuletzt aktualisiert: 26. Okt, 22:10

Credits

vi knallgrau GmbH

powered by Antville powered by Helma


xml version of this page
xml version of this page (summary)

twoday.net AGB

Statistik


about
Codebezogenes
Informatik
Spiele
Technikzeugs
Textformen
Videos und Musik
Zeitgeschehen
Profil
Abmelden
Weblog abonnieren