# Decide whether a DFA accepts the empty language

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?

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

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

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.

• This adds detail to the previous answers -- thanks and +1! Nov 10, 2018 at 22:00

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.

• That's an extremely complicated way of doing it! Reachability of an accepting state is much simpler. Dec 20, 2013 at 7:39
• 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. Dec 20, 2013 at 7:47

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.