Much like the language ALL_DFA that we discussed in class, the language ALL_NFA

Question

Much like the language ALL_DFA that we discussed in class, the language ALL_NFA = { | N is an NFA with some input alphabet sigma, and L(N) = sigma*} is decidable. Consider the language Neither_DFA = { |M_1 and M_2 are DFAs such that there is at least one string x that is accepted by neither M_1 nor M_2}. Prove that Neither_DFA is decidable, using the fact that ALL_NFA is decidable. (In other words, prove that there is an algorithm that can take any two DFAs M_1 and M_2 as input and can always correctly determine whether or not there is at least one string x that is accepted by neither M_1 nor M_2.)

Explanation / Answer

This can be proved by the method of construction.

Make the following construction:

It is decidable to find out whether two DFA's are equivalent. So, it is decidable to find out if DFA found in step 5 and DFA found in step 6 are decidable. If they are decidable, then NFAeither is also decidable.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.