Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
    
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
    
It is just another school of thought. But you are correct; I didn't use it in my solution. –  Zach Langley Mar 21 '11 at 21:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.