How can I prove that $NDFA = \{ \langle M_1,M_2 \rangle | M_1$ and $M_2$ are $DFA$s such that there is at least one string $x$ that is accepted by neither $M_1$ nor $M_2\}$ is decidable using the fact that $ANFA = \{\langle N \rangle | N$ is an $NFA$ with some input alphabet $\Sigma$, and $L(N) = \Sigma^*\}$?


1 Answer 1


We try to decide the language $NDFA$ using a language that decides $ANFA$.

If $x$ is not in neither $L(M_1)$ or $L(M_2)$, then it means that it's not in $L(M_1) \cup L(M_2)$, in other words there is at least one string $x$ which is not in $L(M_1) \cup L(M_2)$, thus $L(M_1) \cup L(M_2) \neq \Sigma^*$ We know that we can (in finite time) construct a $NFA$, $M$ for language $L(M_1) \cup L(M_2)$. Now since $ANFA$ is decidable, $\overline{ANFA}$ is also decidable, so there is a $TM$ that can decide that $L(M) \neq \Sigma^*$, therefor the original language $NDFA$ is also decidable.

  • $\begingroup$ Thanks. I realize I was having difficulty in understanding the neither/nor statement. $\endgroup$
    – N.Ali
    Jun 19, 2017 at 14:30
  • $\begingroup$ @N.Ali, No problem, glad I could help $\endgroup$
    – Karegar
    Jun 21, 2017 at 19:17

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.