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 genau dieselbe Sprache akzeptiert wie ein anderer DFA. Man erhält ihn durch Minimierung eines DFA, also das Entfernen äquivalenter Zustände.^[1]

Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten ${\displaystyle {\mathfrak {A}}}$ akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomaten:^[2]

${\displaystyle u\sim _{L({\mathfrak {A}})}v\Longleftrightarrow (\forall w\in \Sigma ^{*}:uw\in L({\mathfrak {A}})\Leftrightarrow vw\in L({\mathfrak {A}}))}$

Sei ${\displaystyle {\mathfrak {A}}=(Q,\Sigma ,\delta ,q_{0},F)}$ ein deterministischer endlicher Automat. Dann ist ${\displaystyle {\mathfrak {B}}=(Q',\Sigma ,\delta ',q_{0}',F')}$ mit^[3]

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

der Äquivalenzklassenautomat zu ${\displaystyle {\mathfrak {A}}}$.

Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen ${\displaystyle F}$ und ${\displaystyle 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.

• Deterministischer endlicher Automat (DEA)
• Nichtdeterministischer endlicher Automat (NEA)

1. ↑ Konstruktion eines deterministischen endlichen Automaten. Abgerufen am 23. Juni 2025. 
2. ↑ Konstruktion eines deterministischen endlichen Automaten. Abgerufen am 23. Juni 2025. 
3. ↑ Konstruktion eines deterministischen endlichen Automaten. Abgerufen am 23. Juni 2025.