Automatenminimierung

Äquivalenzklassenautomat ist minimal, d.h. besitzt die kleinstmögliche Anzahl von Zuständen

Folgerungen:

• Sei ein Automat mit
• : Verfeinerung von sein, da ansonsten Klassen fehlen:
• Anzahl Zustände von größer oder gleich Anzahl Zustände von
• Zustandszahl von und gleich: Identisch bis auf Isomorphie, d.h. Umbenennung der Zustände

Automat ist nicht minimal, wenn es zwei Zustände gibt:

können verschmolzen werden. Algorithmus: Table-Filling-Algorithmus