2
$\begingroup$

Let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$. Is $X$ Turing decidable? Why or why not?

$\endgroup$
4
$\begingroup$

Re-read your textbook chapter on DFAs and NFAs -- you'll find everything you need to know there.

See also the following questions, which both have answers to your question embedded in their answers (make sure to read carefully):

Next time, tell us what you have tried, to solve the exercise on your own.

$\endgroup$
3
$\begingroup$

So the question you are asking is basically, is there an algorithm that can decide is a DFA accepts no word. I assume you know something about minimizations of DFAs. And you probably know a method how to get from a DFA to a minimal DFA. Such a method can be carried out by a TM.

Now ask yourself, what is the minimal DFA $Y$ for $\emptyset$. Got it? You are left with finding an algorithm that compares the minimization of $ X $ with $Y$, but thats not too hard.

As a remark, the minimization trick works in general if you want to check if two DFAs accept the same language.

$\endgroup$
  • $\begingroup$ That's an extremely complicated way of doing it! Reachability of an accepting state is much simpler. $\endgroup$ – David Richerby Dec 20 '13 at 7:39
  • 2
    $\begingroup$ Well it is basically applying what you know about minimization. We are not talking about the most efficient method here. My method teaches the OP a more general concept of how to handle similar problems. $\endgroup$ – A.Schulz Dec 20 '13 at 7:47
1
$\begingroup$

Show that an NFA accepts at least one word if and only if there is a (directed) path from the initial to an accepting state.

Then it's easy to decide the property, e.g. by BFS from the initial state.

$\endgroup$
1
$\begingroup$

Emptiness problem for DFAs: Given a DFA $D$ determine if $D$ accepts any strings at all, i.e. if $L(D) = ∅$.

The language:

$\qquad E_{DFA}$ = {$\langle D \rangle$ | $D$ is a DFA and $L(D) = ∅$}

Idea for the Turing Machine for $E_{DFA}$:

$\qquad$ Check if any of the accept states are reachable from the start state.

Algorithm for $E_{DFA}$ on input $ D=(Q,Σ,δ,q_0,q_A)$:

$\qquad$ 1) If $D$ is not proper encoding of DFA, reject.

$\qquad$ 2) Mark the start state of $D, q_0$.

$\qquad$ 3) Repeat until no new states are marked:

$\qquad$ $\qquad$ a) Mark any states that can be δ-reached from any marked state.

$\qquad$ 4) If no accept state is marked, accept. Else reject.

Hence, $E_{DFA}$ is decidable as there exists a valid algorithm for it.

$\endgroup$
  • 1
    $\begingroup$ This adds detail to the previous answers -- thanks and +1! $\endgroup$ – David Richerby Nov 10 '18 at 22:00

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.