How to show that $ALL_{DFA}$ is in P

Question

How can I show that $ALL_{DFA}$ is in P ?

$ALL_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \Sigma^* \}$

Answer 1

It is easy to see that a DFA accepts $\Sigma^*$ if and only if all reachable states from the start state, $q_0$, are accepting. This can easily be decided in polynomial-time by performing a breadth- or depth-first search on the DFA from $q_0$. If at any time a non-accepting state is visited, reject, otherwise, if only accepting states are found, accept.

Note that this problem is much harder for NFAs; $\{ \langle A \rangle \mid A \text{ is an NFA and } L(A) = \Sigma^* \}$ is NP-hard.