Why is E(dfa) a decidable language?

Question

I don't understand why the Turing Machine T, ACCEPTS when no accept state is marked and rejects when an accept state is marked:

E(dfa) = {| A is a DFA and L(A) = the empty set(don't have the symbol)}

E(dfa) is a decidable language.

Proof: A DFA accepts some string iff reaching an accept state from the start state by >traveling along the arrows of the DFA is possible. To test this condition, we can design a >TM T that uses a marking algorithm similar to that used in Example 3.23.

T= "On input , where A is a DFA: 1. Mark the start state of A. 2. Repeat until no new states get marked: 3. Mark any state that has a transition coming into it from any state that is already marked. 4. If no accept state is marked, accept; otherwise, reject."

This seems backwards to me. Can anyone explain this?

Thank you.

Answer 1

I believe that your confusion results from the use of the words "accept" and "reject" in different contexts. At a high level, it's easy to avoid this confusion, because you can define your Turing machine, T to not refer to the process a DFA, A, does its own accepting and rejecting.

L(T) is { A | L(A) is empty }. This is the same as E(dfa) defined in your question, but using L(T) makes it more explicit that we're dealing with two separate languages here, one just happens to be defined in terms of another.

If we work from high-level to low-level, we can say:

• L(T) accepts A whenever L(A) is empty.
• But how do we determine whether L(A) is empty? Well L(A) is empty when A rejects all strings.
• How do we know a string is rejected in A? It does not end in an accept state.

We can also work from low to high now quite easily:

• If a string given to A does not end in an accept state, it is rejected.
• If all strings are rejected by A, then L(A) is empty.
• If L(A) is empty, then L(T) accepts A.

Now your proof goes into a bit more detail as to how T goes about deciding whether to accept A or not, but I think your confusion revolved more around the multiple uses of accept and reject. Very broadly, you can say T accepts A iff A rejects everything.