Reduzierung eines endlichen Automaten

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.