I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation").

Can I just use the given $M$ as a decider?

$M =$ "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is an empty string ($L(w)=\emptyset$):

  1. Mark the start of the DFA as $q_0$.
  2. Simulate B on input w a finite number of times:
    1. First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
    2. Recursively: mark states that can be obtained within a finite $δ$ operations from any marked states.
  3. If no accept state marked - accept. else, reject."

Is this correct?

Definitions: $$\begin{align*} A_{DFA} &= \left\{ \langle B,w \rangle \mid \text{$B$ is a DFA that accepts input string $w$} \right\} \\ E_{DFA} &= \left\{ \langle A \rangle \mid \text{$A$ is a DFA and $L\left(A\right) = \varnothing$} \right\} \end{align*}$$

Emphasis: I am trying to prove $E_{DFA}$ by running the proof of $A_{DFA}$ several times (finite), so I thought the correct thing would be to use the input $w$ as empty set.

  • 1
    $\begingroup$ Note you can use \langle and \rangle instead of < and >, respectively, and which are much better to read. $\endgroup$
    – dkaeae
    Apr 8, 2019 at 15:44
  • 2
    $\begingroup$ If the DFA has $n$ states and accepts some word, then it accepts some word of length less than $n$. $\endgroup$ Apr 8, 2019 at 17:33
  • $\begingroup$ would appreciate what is the correct way to do so. i am really unsure above what i've written and it is intriguing me a lot $\endgroup$ Apr 8, 2019 at 19:58
  • $\begingroup$ I'm not sure what the notation $L(w) = \emptyset$ means. The operator $L$ maps a DFA to a language. The input is not a word. In the text, you mention that you want to use the empty set for the input $w$, but the empty set is not a word. $\endgroup$ May 22, 2019 at 14:14

1 Answer 1


If you want to reduce $E_{DFA}$ to $A_{DFA}$, you should use the following theorem:

If a DFA with $n$ states accepts some word, then it accepts some word of length less than $n$.

But a much more efficient algorithm would just run DFS from the initial state, and check whether some accepting state is reachable from it.


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.