Material OOP Grundlagen Delphi Software-Technik Bonsai Digitaltechnik Ereignisse Grafik UML Netze Fischertechnik Tipps Werkzeuge Literatur Automaten Sprachen Datenbanken XML Prolog Berechenbarkeit
Pfad: Startseite / Fächer / Informatik / Material
Autor: mk
09.08.2008 12:03
8841

Minimierung eines DFA

Beispiel 1 aus dem "Exorciser"

Minimierung mit JFlap

Noch bevor der Minimier-Algorithmus von JFlap loslegt, lässt er mal gleich einen Teil des Automaten weg.

Warum? Lösung

Idee

Äquivalente Zustände werden "verschmolzen".

Dabei sind Zustände äquivalent, wenn sie für jedes Wort ein gleiches "Akzeptanzverhalten" des Automaten bedingen. Das heißt, kommt man mit einem Wort (einer Folge von Eingaben) aus dem einen Zustand (von zwei äquivalenten) in einen Endzustand, so auch aus dem anderen und umgekehrt. Das Gleiche gilt für nicht akzeptierende Zielzustände.

Das bedeutet umgekehrt, dass schon ein Wort die "Nicht-Äquivalenz" zweier Zustände belegen kann. Das leere Wort ε führt zu keinem Zustandsübergang, belegt aber schon die Nicht-Äquivalenz von End- und Nicht-End-Zuständen.

Gerät man mit einem Wort von zwei zu untersuchenden Zuständen in zwei bereits als nicht- äquivalente bekannte Zustände, so belegt dieses Wort die Nicht-Äquivalenz der Zustände. So erkennt man durch Ausprobieren immer längerer Worte die Nichtäquivalenz von Zuständen. Die Worte brauchen dabei nicht länger als die Anzahl der Zustände gewählt werden.

siehe auch: Schönig, Theoretische Informatik-kurzgefasst, 4.Auflage, S.46

Übrig bleiben unter Umständen Zustände, deren Nicht-Äquivalenz mit keinem Wort ∅ belegt werden kann, sie werden unter Mitnahme der Transitionen verschmolzen.

Beispiel 2 aus dem "Exorciser"

exor2.jff

Algorithmus

Schönig, Theoretische Informatik-kurzgefasst, 4.Auflage, S.46

  1. Stelle eine Tabelle aller Zustandspaare {z,z'} mit z ≠ z' auf.
  2. Markiere alle Paare {z,z'} wobei z Endzustand und z' kein Endzustand oder umgekehrt.
  3. Für jedes unmarkierte Paar {z,z'} und für jede Eingabe a teste, ob das Paar der Folgezustände bereits markiert ist. Wenn ja, markiere auch {z,z'}.
  4. Wiederhole Schritt 3, bis sich keine Änderung mehr in der Tabelle ergibt.
  5. Alle nicht markierten Paare {z,z'} können jeweils zu einem Zustand verschmolzen werden.

Aufgabe 1

Minimiere folgenden Automaten (Exorciserdatei: bsp1.exo).

Aufgabe 2

Minimiere folgenden Automaten (Exorciserdatei: bsp2.exo).

Valid XHTML 1.0! lokal