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.

Name

Url

Meine Eingaben merken?

Titel:

Text:


JCaptcha - du musst dieses Bild lesen können, um das Formular abschicken zu können
Neues Bild

 

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