Let A = { | M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable.

The questions seems simple so I designed the following TM D that decides whether there exists a DFA with this property or not.

D = "On input w:

  1. Construct a DFA B that accept any string containing an odd number of 1s.
  2. Construct a DFA C s. t. $L(C) = L(B) \cap L(M)$
  3. Call $E_{DFA}$ with input C.
  4. If T accepts, then reject. If T rejects, then accept."

$E_{DFA}$ is defined as following: $E_{DFA} = \{ <A> |$ A is a DFA and L(A) = $\phi \}$ So assume there is a TM T that decides language $E_{DFA}$. I.e., T accepts if A is empty, otherwise rejects.

Now, my questions is related to the step 4. In Sipser's textbook, he states that if T accepts, then accept and if T rejects, then reject. I don't understand why it says so. For example, If $L(M) \cap L(B) = \phi$, then this means that there are different. So, this is what I said in step 4 above. But in Sipser's answer for this exercise in page 187, it says that if they are empty, then accept. Can you explain to me where is my mistake?


1 Answer 1


If $E_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$. In other words, no word containing an odd number of 1s is also in $L(M)$. Then, by definition of $A$ you should accept.

Conversely, if $E_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B \neq \emptyset$. That is, there is some word $w \in L(M)$ such that $w$ contains an odd number of 1s. Then, by definition of $A$, you should reject.

  • $\begingroup$ Thank you Steven! I think my mistake was not taken carful look at definition of A. I thought it accept any string with odd number of 1s. $\endgroup$
    – user777
    Mar 24, 2021 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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