# prove that NDFA = {< M1,M2 > | M1 and M2 are DFAs such that there is at least one string x that is accepted by neither M1 nor M2} is decidable?

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^*\}$?

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.

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