# 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}$? Mar 20, 2011 at 22:51
• @Mitch: Edited. Mar 21, 2011 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. Mar 21, 2011 at 20:33
• It is just another school of thought. But you are correct; I didn't use it in my solution. Mar 21, 2011 at 21:42
• Why is your last claim so, given that an NFA can be converted into a DFA? Dec 4, 2021 at 21:57
• @actinidia DFAs can be exponentially larger than their NFA counterparts, so converting to a DFA does not give a polynomial-time algorithm. Dec 6, 2021 at 3:04

We create a TM F that decides the problem in polynomial time on input $$D$$, a DFA, with final states $$F$$ and states $$D$$.

F: On input $$$$

1. Accept if $$F = Q$$
2. Check if there is at least one state in $$Q - F$$ that is reachable using BFS.
3. If there is no such state, accept, otherwise reject.

So F decides $$ALL_{DFA}$$ since it accepts iff $$D$$ accepts $$\Sigma^*$$, and it is polynomial since we use BFS, it takes at most $$O(n)$$.

Since D is a DFA, and if every reachable state in D accepts, so D must accept all possible strings. If a non-accepting reachable state exists, then there must be some string that D doesn't accept. 