Minimaler Automat |
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.
|
|---|
äquivalente Zustände |
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.
|
|
hieraus folgt, dass Endzustände und Nicht-Endzustände nicht äquivalent sind. Die einen akzeptieren das leere Wort, die anderen nicht.
|
|
diese Äquivalenzklassen bilden die neue, minimale Zustandsmenge.
|
Algorithmus |
zur Minimierung
|
.1 |
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.
|
.2 |
wiederhole den folgenden Schritt für alle Mengen
der Partition und für alle Zeichen des
Eingabealphabets bis keine feinere
Partitionierung mehr entsteht:
|
.3.a |
wähle eine Menge P aus der Partition und ein
Eingabezeichen i.
|
.3.b |
Berechne für alle
Zustände q aus der
Menge P die
Menge P' aus
der Partition, in der
delta(q,i) liegt.
|
.3.c |
Fasse alle Zustände
qi aus P zu Mengen Pneu zusammen, für die
delta(qi,i) in der
gleichen Partitionsmenge P' liegt.
|
.3.d |
liefert dieser Prozess mehrere Mengen Pneu,
so entferne P aus der Partition und füge alle Pneu-Mengen hinzu.
|
|
|
1. Beispiel |
(aa)*|(aaa)*
|
|
alle Wörter mit einer geraden oder durch 3 teilbaren Anzahl von a's.
|
|---|
der NFA |
|
|
|
der DFA |
|
|
die Zustände 1 und 7 sind äquivalent, sie können zusammengefasst werden
|
|---|
|
|
der minimale DFA |
|
|
die "natürliche" Lösung
|
|---|
|
|
2. Beispiel |
c*a(a|c)*b(a|b|c)*
|
|
alle Wörter, in denen das 1. a vor dem 1. b steht
|
|---|
der DFA |
|
|
|
der minimale DFA |
|
|
die Zustandsmenge kann von 6 auf 3 Zustände reduziert werden
|
|---|
|
|
3. Beispiel |
((b|c)*a(b|c)*a)*(b|c)*
|
|
Alphabet A = {a, b, c}
alle Wörter mit gerader Anzahl von a's
|
|---|
der DFA |
|
|
|
der minimale DFA |
|
|
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.
|
|
|
Compilerbau & Formale Sprachen: Minimale deterministische endliche Automaten
