Minimale deterministische endliche Automaten

Bei der Transformation von regulären Ausdrücken über nichtdeterministische endliche Automaten in deterministische endliche Automaten entstehen häufig nicht die einfachst-möglichen endlichen Automaten.

Es ist häufig möglich, einen kleineren äquivalenten Automaten zu finden, d.h. einen Automaten mit weniger Zuständen, der aber die gleiche Sprache akzeptiert.

um einen minimalen Automaten zu konstruieren, muss man äquivalente Zustände zusammenfassen. Zwei Zustände sind äquvalent, wenn über sie die gleiche Menge von Wörtern akzeptiert wird.

Sei ein Automat A = (Q, I, q₀, δ, F) gegeben.

Zwei Zustände q₁ und q₂ sind genau dann äquivalent, wenn gilt: die Automaten

A₁ = (Q, I, q₁, δ, F)

und

A₂ = (Q, I, q₂, δ, F)

akzeptieren die gleiche Sprache, d.h. A₁ und A₂ sind äquivalent

hieraus folgt, dass Endzustände und Nicht-Endzustände nicht äquivalent sind. Die einen akzeptieren das leere Wort, die anderen nicht.

Die Partitionierung in Mengen äquivalenter Zustände bildet die Zustandsmenge des minimalen Automaten.

zur Minimierung

partitioniere die Zustandsmenge in die beiden Teilmengen der Endzustände und Nicht-Endzustände. Diese Ausgangspartitionierung wird schrittweise verfeinert, bis alle Mengen nur noch äquivalente Zustände enthalten.

wiederhole den folgenden Schritt für alle Mengen der Partition und für alle Zeichen des Eingabealphabets bis keine feinere Partitionierung mehr entsteht:

wähle eine Menge P aus der Partition und ein Eingabezeichen i.

Berechne für alle Zustände q aus der Menge P die Menge P' aus der Partition, in der delta(q,i) liegt.

Fasse alle Zustände q_i aus P zu Mengen P_neu zusammen, für die delta(q_i,i) in der gleichen Partitionsmenge P' liegt.

liefert dieser Prozess mehrere Mengen P_neu, so entferne P aus der Partition und füge alle P_neu-Mengen hinzu.

(aa)*|(aaa)*

alle Wörter mit einer geraden oder durch 3 teilbaren Anzahl von a's.

die Zustände 1 und 2 sind äquivalent, sie können zusammengefasst werden

Die "natürliche" Lösung:
Ein Automat, der modulo 6 zählt und sich bei 0,2,3 und 4 a's in einem Endzustand befindet.

c*a(a|c)*b(a|b|c)*

alle Wörter, in denen das 1. a vor dem 1. b steht

die Zustandsmenge kann von 6 auf 3 Zustände reduziert werden

((b|c)*a(b|c)*a)*(b|c)*

Alphabet A = {a, b, c}
alle Wörter mit gerader Anzahl von a's

die Zustandsmenge kann von 5 auf 2 Zustände reduziert werden, und es entsteht der Automat, den man auch per Hand konstruieren würde.

Die Minimierung wird in Scanner-Generatoren durchgeführt, um die Übergangstabelle zu verkleinern, diese steigt vom Platzbedarf linear mit der Anzahl der Zustände. Auf die Geschwindigkeit der Automaten hat diese Optimierung keinen Einfluss.