Minimierung
BearbeitenZu jedem DEA existiert ein eindeutiger minimaler Automat, der die gleiche Sprache akzeptiert.
Da die Zustände des Minimalautomaten den Äquivalenzklassen der vom endlichen Automaten akzeptierten Sprache unter der Nerode-Relation entsprechen, spricht man auch vom Äquivalenzklassenautomat:
Sei ein deterministischer endlicher Automat. Dann ist mit
![{\displaystyle Q'={\Big \{}[w]_{L(M)}\mid w\in \Sigma ^{*}{\Big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03dccf2c6407fe28738a2a79b2359c5763b1d287)
![{\displaystyle ~q'_{0}=[\epsilon ]_{L(M)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89e6ed79ac1317f381a0bd3a2e470a52ab832d90)
![{\displaystyle ~\delta '([u]_{L(M)},a)=[ua]_{L(M)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0aab3753a7fab957a2c2615e4b73d1012945e06)
![{\displaystyle F'={\Big \{}[u]_{L(M)}\mid u\in L(M){\Big \}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/502fa79fc98b156549cb77f6555baf4cd88cfff6)
der Äquivalenzklassenautomat zu .
Die Minimierung eines deterministischen Automaten kann algorithmisch durch fortwährende Verfeinerung der Äquivalenzklassen gelöst werden. Man beginnt mit den Zustandsmengen und . 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.
