# Proving $E_{DFA}$ is decidable by running $A_{DFA}$ several times

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.

• Note you can use \langle and \rangle instead of < and >, respectively, and which are much better to read. – dkaeae Apr 8 '19 at 15:44
• If the DFA has $n$ states and accepts some word, then it accepts some word of length less than $n$. – Yuval Filmus Apr 8 '19 at 17:33
• 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 – CrimsonWater Apr 8 '19 at 19:58
• 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. – Yuval Filmus May 22 '19 at 14:14

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$$.