Zur Themenwahl

Zustandsreduktion eines Mealyautomaten

 

Minimal-Mealy-Automaten

Sei A(x,y,z,δ,λ) ein Mealyautomat.

Eine beliebige Eingabefolge von x-Werten sei p. z ist ein gegebener Zustand. Dann ist
λ(z,p)=λ _(z)(p) die zu z gehörende Ausgabefolge von y-Werten.

λ _(z) sei die Abbildung, die für alle Eingabenfolgen und gegebenes z die Ausgabefolgen angibt. Diese Abbildung heißt die vom Zustand z erzeugte Abbildung.

Die Menge { λ _(z)|z ε Z} wird Abbildungsfamilie des Automaten genannt.

 

Definition
Zwei Zustände heißen äquivalent, wenn sie die gleiche Abbildung erzeugen.
Zwei Automaten werden äquivalent genannt, wenn die von ihnen erzeugten Abbildungsfamilien gleich sind.

 

Hauptsatz
Jeder Automat der Menge aller zu einem Automaten äquivalenten Automaten lässt sich (bis auf Umbenennungen) eindeutig auf einen Automaten mit minimaler Zustandszahl abbilden (Minimalautomat). Die Zustände dieses Minimalautomaten sind paarweise inäquivalent zu einander.

Anmerkung: Der Beweis des Satzes lässt sich analog dem Verfahren durchführen, das im folgenden Beispiel angegeben wird.

 

Ein Beispiel für die Erzeugung des Minimalautomaten

Die gegebene δ,λ-Tafel eines Mealyautomaten wird schrittweise zur Tafel des Minimalautomaten umgeformt.

    Zur Themenwahl