How would one go about proving/disproving the language $\{\langle A\rangle \mid A\text{ 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?
The answer is yes, I think. Tell me whether you think my proof is correct.
I will prove that if an $n-$ state DFA recognizes all binary strings of length $\le n-1$ then it recognizes all binary strings. This will prove the theorem, for the Turing machine first converts the input NFA to a DFA. It the resulting DFA has $n$ states, the Turing simulates the action of the DFA on all bit strings of length $\le n-1,$ and accepts it if and only if all strings are accepted.
Now for the proof. The DFA accepts $\varepsilon,$ so the starting state is an accepting state. Since $0$ and $1$ are accepted, any state directly reachable from the starting state is accepted. Continuing is this manner, we see that every state reachable from the start in at most $n$ steps is accepting. But there are only $n$ states, so every reachable state is reachable in at most $n-1$ steps, and every state is accepting.
EDIT My proof originally said, "Every state is reachable in at most $n+1$ transitions," but it should have said,"Every reachable state is reachable in at most $n-1$ transitions." This isn't important, because the NFA-to-DFA algorithm can prune unreachable states, and if the statement is true for $n-1$ it's true for $n+1,$ but I'm adding the argument if only to reassure myself.
Let T be a reachable state of the DFA, and consider the states visited in processing a string of minimal length that leads to T. No state is visited twice, because if we visit a state U twice, we can remove the substring processed between the two visits from the input and get a shorter string leading to T. Since there are no more than $n$ states on the path, there are at most $n-1$ transitions.