# Show that ALL DFA is decidable

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?

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

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.