Minimierung eines DEA

Drucken

Das Ergebnis der Umwandlung eines nichtdeterministischen Automaten (NEA) in einen deterministischen Automat (DEA) liefert oft ein noch verbesserbares Ergebnis. Diese Verbesserung kann durch einen Algorithmus erreicht werden. (Table Filling Algorithm) . Gegeben sei der folgende Automat:

Der erste Schritt besteht darin, alle Zustände zu entfernen, die nicht errreichbar sind. Folgend wird eine Tabelle, wie unten links dargestellt, aufgebaut. Es werden alle Paare markiert, die nur einen Endzustand enthalten (unvereinbar). Im vorstehenden Fall wären es alle Paare von Zuständen, die den Zustand S4 enthalten. Im Anschluss daran wird überprüft ob ein Paar von Zuständen in ein Paar von Zuständen übergeht, welches ebenso einen Endzustand enthält, trifft dies zu, wird dieser Zustand in die Menge der markierten Zustände aufgenommen. Nach mehrfachem Durchlauf dieses Algorithmus erhält man die Restmenge der vereinbaren unmarkierten Zustände, unten rechts dargestellt.

Der entstandene Automat ist der Folgende.

 


   Beschreibung

   Kurzform der Lösung