NP-complete decision problems on deterministic automata
The decision version of the DFA identification problem  (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:

Input: Integer $k$ and sets $P, N \subseteq \Sigma^*$

Question: Is there a DFA $A$ with at most $k$ states such that $P \subseteq L(A)$ and $N \cap L(A) = \emptyset$. In other words $A$ accepts all words in $P$ and rejects all words in $N$.

See: E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302–320, June 1978