von unerreichbaren Zuständen und äquivalenten Zuständen freier deterministischer oder nichtdeterministischer Automat.

Dabei ist ein Zustand z unerreichbar, wenn es keine Eingabe gibt, durch die der Automat aus einem Anfangszustand in z überführt wird. Zwei Zustände sind äquivalent, wenn jede Eingabe bei z zur gleichen Ausgabe führt wie bei z^′, und jede Eingabe z in einen Endzustand überführt genau dann, wenn sie z^′ in einen Endzustand überführt. Zu jedem Automaten gibt es einen äquivalenten minimalen Automat, der im endlichen deterministischen Fall durch Weglassen unerreichbarer und Verschmelzen äquivalenter Zustände effizient konstruiert werden kann. Zu einem deterministischen endlichen Automaten gibt es einen bis auf Isomorphie eindeutigen minimalen Automaten, dessen Zustandszahl (bei ausgabefreien Automaten) gerade der Zahl der Äquivalenzklassen der Nerode–Äquivalenz entspricht.

Die Minimierung von Automaten erlangt durch die vielfältige Verwendung von Automaten in der Informatik besondere Bedeutung.