2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note you can use \langle and \rangle instead of < and >, respectively, and which are much better to read. $\endgroup$ – dkaeae Apr 8 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$ – Yuval Filmus Apr 8 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$ – CrimsonWater Apr 8 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$ – Yuval Filmus May 22 at 14:14
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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