Minimalautomat

Ein Minimalautomat oder minimierter Automat (englisch minimal finite automaton oder minimal deterministic finite automaton, DFA) ist in der theoretischen Informatik ein endlicher Automat mit minimaler Zustandsanzahl der eine gegebene reguläre Sprache akzeptiert.

Diese reguläre Sprache ist typischerweise als DFA gegeben. Man erhält den Minimalautomat dann durch Minimierung des gegebenen DFA, also durch das Zusammenfassen äquivalenter Zustände.

Definition

Um einen Minimalautomat für eine reguläre Sprache $R$ mit Alphabet $\Sigma$ zu definieren, nutzt man eine Äquivalenzrelation, die Nerode-Relation, die Wörter der Sprache in Äquivalenzklassen einteilt. Zwei Wörter $u,v$ werden in der Sprache $R$ als äquivalent betrachtet, notiert als $u\sim _{R}v$ , wenn für jedes Suffix $z\in \Sigma ^{*}$ gilt, dass entweder (a) sowohl $uw$ als auch $vw$ in der Sprache $R$ sind oder (b) weder $uw$ noch $vw$ in der Sprache $R$ ist.

u\sim _{R}v\Longleftrightarrow (\forall w\in \Sigma ^{*}:uw\in R\Leftrightarrow vw\in R)

Die Äquivalenzklasse eines Wortes $w\in \Sigma ^{*}$ notieren wir als $[w]_{R}$ .

Diese Äquivalenzklassen bilden die Zustände des Minimalautomaten, man spricht auch vom Äquivalenzklassenautomaten. Der Startzustand ist die Äquivalenzklasse $[\epsilon ]_{R}$ des leeren Worts und die Endzustände sind die Äquivalenzklassen der Wörter der Sprache $R$ . Die Übergangsfunktion $\delta '$ ergibt sich als $\delta '([u]_{R},a)=[ua]_{R}$ für $u\in \Sigma ^{*},a\in \Sigma$ .

Formale Definition

Sei ${\mathfrak {A}}=(Q,\Sigma ,\delta ,q_{0},F)$ ein deterministischer endlicher Automat und $R$ die reguläre Sprache von ${\mathfrak {A}}$ . Dann ist ${\mathfrak {B}}=(Q',\Sigma ,\delta ',q_{0}',F')$ mit

$Q'={\Big \{}[w]_{R}\mid w\in \Sigma ^{*}{\Big \}}$
$~q'_{0}=[\epsilon ]_{R}$
$~\delta '([u]_{R},a)=[ua]_{R}$
$F'={\Big \{}[u]_{R}\mid u\in R{\Big \}}$

der Äquivalenzklassenautomat zu ${\mathfrak {A}}$ bzw. $R$ .

Herstellung

Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen $F$ und $Q-F$ . Für jeden Buchstaben aus dem Alphabet wird nun jede Zustandsmenge dahingehend aufgeteilt, dass die Überführungsfunktion die Zustände jeder neuen Menge den Buchstaben in eine jeweils eindeutige Menge abbildet. Dies wird so oft wiederholt, bis sich keine Änderung mehr ergibt.

Es besteht außerdem die Möglichkeit, minimale deterministische endliche Automaten inkrementell aufzubauen. Inkrementell bedeutet hier, dass die zu akzeptierenden Worte einzeln dem Automaten hinzugefügt werden. Nach jedem Einfügen eines solchen Wortes ist der deterministische endliche Automat minimal. Dieses Verfahren ist vor allem dann erfolgversprechend, wenn die Worte häufig gemeinsame Prä- und Suffixe teilen, dies ist z. B. bei Worten aus natürlichen Sprachen der Fall.

Algorithmus zur Minimierung eines DEA

Gegeben: DEA ${\mathfrak {A}}=(Q,\Sigma ,\delta ,q_{0},F)$

Berechne: Minimalautomat ${\mathfrak {B}}=(Q',\Sigma ,\delta ',q_{0}',F')$

Entferne Zustände aus $Q$ die nicht vom Startzustand $q_{0}$ erreichbar sind.

Betrachte alle Zustandspaare $(q,q')$ mit $q,q'\in Q,q\not =q'$ auf.

Markiere alle Paare die genau einen $(q,q')$ Endzustand enthalten, d. h. $q\in F,q'\notin F$ oder $q\notin F,q'\in F$ , als nicht äquivalent.

Durchlaufe alle unmarkierten Paare $(q,q')$ und alle Eingaben $a\in \Sigma$ : Wenn das Paar $(\delta (q,a),\delta (q',a))$ schon markiert ist, dann markiere $(q,q')$ als nicht äquivalent.

Falls es im letzten Schritt Änderungen gab: Wiederhole den letzten Schritt.

Für alle unmarkierten Paare $(q,q')$ gilt, dass diese zwei Zustände äquivalent sind. Wir notieren die Äquivalenzklasse eines Zustands $q$ als $[q]$ .

Verschmelze äquivalente Zustände zu einem einzelnen Zustand, d. h.:

$Q'=\{[q]\mid q\in Q\}$
Neue Übergangsfunktion: $\delta '([q],a)=[\delta (q,a)]$
Neuer Startzustand: $~q'_{0}=[q_{0}]$
Neue Endzustände: $F'=\{[q]\mid q\in F\}$

Dieser Algorithmus kann so implementiert werden das die Laufzeit in $O(|Q|^{2}\cdot |\Sigma |)$ liegt^[1].

Siehe auch

Literatur

Uwe Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage. Spektrum, München 2008, ISBN 978-3-8274-1824-1, 1.2.5. Äquivalenzrelationen und Minimalautomaten.
Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 4.2. Die Minimierung endlicher Automaten.