How would one go about proving/disproving the language {⟨A⟩∣A is an NFA and L(A)={0,1}∗} is/isn't decidable?
I assumed at first since it was an NFA involved it would be decidable, but since there is no input string to simulate does this change things? If so, how? I can't think of a turing machine that would decide this. Since {0, 1}* is theoretically infinite does mean a turing machine may never halt thus the language is undecidable? If so how do I go about proving this?
Speaking informally, you can show this by constructing a Turing Machine constructs a DFA D_A equivalent to NFA A. It then constructs the DFA D_0 that accepts the language {0,1}*, we can then simulate the decider for EQ_DFA on .
Formally speaking, construct TM S: S = "On input :