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$):
- Mark the start of the DFA as $q_0$.
- Simulate B on input w a finite number of times:
- First check if the encoding is correct, if $L(w)=\emptyset$, if not - reject.
- Recursively: mark states that can be obtained within a finite $δ$ operations from any marked states.
- 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.
\langle
and\rangle
instead of<
and>
, respectively, and which are much better to read. $\endgroup$ – dkaeae Apr 8 '19 at 15:44