We essentially show that minimizing finite automata is NP-hard as soon as one deviates from the class of deterministic finite automata. More specifically, we show that minimization is NP-hard for all finite automata classes that subsume the class that is unambiguous, allows at most one state
with a non-deterministic transition for at most one alphabet symbol
, and is allowed to visit state
at most once in a run. Furthermore, this result holds even for automata that only accept finite languages.