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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Note you can use \langle and \rangle instead of < and >, respectively, and which are much better to read. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented May 22, 2019 at 14:14

1 Answer 1

Reset to default
2
$\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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.