Suche Home Einstellungen Anmelden Hilfe  

Minimierung 4: Allgemeines Verfahren, Algorithmus zur Feststellung äquivalenter Zustände

Elemente einer Äquivalenzklasse zeigen das gleiche funktionale Verhalten in Bezug auf Konkatenation eines Wortes w
Bei der Suche nach verschmelzbaren Zuständen werden Eigenschaften von Äquivalenzklassen berücksichtigt. Die Teilwörter u und v sind in den Zuständen p und q abgearbeitet. Wird nun jeweils ein Teilwort w angehangen und es entstehen in beiden Fällen Wörter, die nicht in der Sprache liegen, oder in beiden Fällen Wörter, die in der Sprache liegen, dann ist nicht wichtig, ob das Wort in unterschiedlichen Endzuständen akzeptiert wurde.

Diese Eigenschaft nutzt der Algorithmus. Von Endzuständen ausgehend arbeitet er sich bis zum Startzustand vor. Dabei wird überprüft, ob von den verglichenen Zustandspaaren aus unterschiedliche Analysen eines Wortes möglich sind.

Für jeden DEA M gibt es einen M' mit minimal vielen Zuständen, der die gleiche Sprache akzeptiert, also L(M)=L(M').
Das Verfahren sucht nach Äquivalenzklassen. Es wird ausgenutzt, dass sich äquivalente Teilwörter in Bezug auf Konkatenation funktional gleich verhalten.

Algorithmus zum Auffinden der verschmelzbaren Zustände (indistinguishable states)
E: DEA M = (Q,Sigma,delta,q0,F}) ohne überflüssige Zustände (s. Reduktion).1 
A: Verschmelzbare Zustände (ohne Markierung)

  1. Bilde Tabelle mit Zustandspaaren {q,q'} und qungleichq'

  2. Eine halbe Matrix reicht hier aus, da die Reihenfolge im Paar keine Rolle spielt, {q,q'} = {q',q}. 
  3. Markiere alle Paare {q,q'}, bei denen einer(!) Endzustand ist und der andere nicht.

  4. In dem Fall sind q und q' auf keinen Fall äquivalent. Dies ist unsere Initialisierung.
  5. Für jedes unmarkierte Paar und jedes a aus Sigma tue folgendes: 
    • markiere das Paar, wenn das Paar {delta(q,a), delta(q',a)} bereits markiert ist;
    bis keine weitere Änderung mehr eintritt.
    Vorgehen von "hinten": q und q' sind dann äquivalent, wenn sie in ein verschmelzbares Zustandspaar = in einen Zustand hineinführen
  6. Die noch unmarkierten Zustandspaare sind jeweils verschmelzbar.
Das Verfahren kann mit der Komplexität O(|Q|2) implementiert werden.
____
1 Bitte beachten Sie, dass Automaten immer vollständig definiert sind (Konzept: absorbierender Zustand). Insofern sind Graphdarstellungen oft vereinfacht.

Äquivalenzklassen 1   2   3   4   5  6 Beispiel

Benutzer: Gast • Besitzer: senn • Zuletzt geändert am: