0
$\begingroup$

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given $$\text{ALL}_{\text{DFA}} =\{\langle A\rangle \mid A\text{ is a DFA and }L(A)=\text{Σ*}\}$$ prove that $\text{ALL}_{\text{DFA}}$ is decidable.

The following is my solution:

On input <A>:
1. Build a DFA D such that L(D)=Σ*
2. Execute EQ DFA on <A, D>
3. Return the output

Can this be considered a valid solution?

$\endgroup$
1
  • 4
    $\begingroup$ This is overkill. You can just determine whether some non-accepting state is reachable from the initial state. This runs in linear time. $\endgroup$ Apr 7, 2022 at 14:20

2 Answers 2

0
$\begingroup$

Your approach to the answer is absolutely correct. But you can make it in linear run time. steps: 1.First check for the unreachable final states and remove them. 2.from now you can solve from your approach.

$\endgroup$
0
$\begingroup$

Yes, it is a valid solution. Note that it is sufficient to check whether $L(D)\subseteq L(A)$. Also, note that since you can take D to be an accepting-sink, $q_{acc}$, then checking language containment by checking whether the product $\{q_{acc}\}\times A$ has a reachable state of the form $(q_{acc}, s)$, where $s$ is rejecting, is essentially the same as checking if there is a reachable rejecting state in $A$. So this should give you a hint that there is no need to reduce your problem to language containment, as pointed out by others.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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