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

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^* \}$

-
What is $ALL$? (presumably $DFA$ is determinsitic finite automaton). And then what is their relation in $ALL_{DFA}$? –  Mitch Mar 20 '11 at 22:51
@Mitch: Edited. –  metdos Mar 21 '11 at 7:14
Note 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.
Interestingly, this problem is much harder for NFAs; $\{ \langle A \rangle \mid A \text{ is an NFA and } L(A) = \Sigma^* \}$ is NP-hard.
I have understood edit part. Apart from that I could not see how using $\overline{ALL_{DFA}}$ additionally helps. –  metdos Mar 21 '11 at 20:33