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^* \}$
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^* \}$
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.
My answer to this problem on a recent homework was originally similar to the other answer on this question: Perform a breadth first search on the input, If a non-accept state is visited reject, Otherwise accept. However, this solution is wrong. This decider will accept a DFA that does not accept all inputs if, for example, there is no transition for one of the characters in Σ. The following DFA (with an alphabet of 0 and 1) is an example of this. It will not accept inputs with a 1, but there is no reject state that will cause this DFA to be rejected by the decider.
The answer is actually to construct the complement to the input and test whether the language of the complement is an empty set. You can do this by doing a breadth or depth first search on the complement and if an accept state is found, reject the input and otherwise, accept.