Reduzierung eines endlichen Automaten
Einen reduzierten endlichen Automaten erhält man indem man tut, was folgender Algorithmus zur Reduzierung endlicher Automaten besagt:
- streiche alle nicht erreichbaren Zustände aus der Zustandsmenge
- bestimme die Äquivalenzklassen der verbleibenden Zustände, d.h. erstelle Klassen äquivalenter Zustände
- ersetze alle Zustände einer Äquivalenzklasse durch nur einen Repräsentaten, d.h. ersetzte die gesamte Klasse durch nur einen Zustand.