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^* \}$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is $ALL$? (presumably $DFA$ is determinsitic finite automaton). And then what is their relation in $ALL_{DFA}$? $\endgroup$– MitchMar 20, 2011 at 22:51
-
$\begingroup$ @Mitch: Edited. $\endgroup$– metdosMar 21, 2011 at 7:14
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ I have understood edit part. Apart from that I could not see how using $\overline{ALL_{DFA}}$ additionally helps. $\endgroup$– metdosMar 21, 2011 at 20:33
-
$\begingroup$ It is just another school of thought. But you are correct; I didn't use it in my solution. $\endgroup$ Mar 21, 2011 at 21:42
-
1$\begingroup$ Why is your last claim so, given that an NFA can be converted into a DFA? $\endgroup$ Dec 4, 2021 at 21:57
-
2$\begingroup$ @actinidia DFAs can be exponentially larger than their NFA counterparts, so converting to a DFA does not give a polynomial-time algorithm. $\endgroup$ Dec 6, 2021 at 3:04
$\begingroup$
$\endgroup$
1
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 $<D>$
- Accept if $F = Q$
- Check if there is at least one state in $Q - F$ that is reachable using BFS.
- 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.
-
1$\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$– Community BotMay 21 at 11:05
$\begingroup$
$\endgroup$
1
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.
-
2$\begingroup$ Factually what you are saying is wrong : a DFA must have a complete transition function by complete i mean that for any state you have a transition for any element of the alphabet to an other states. This come from the Definition of a DFA if it's not the case then you work on a NFA. $\endgroup$– user338772May 11, 2016 at 13:49