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,

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.)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
