computer-scienceturing-machinesdecidable

Is the language {⟨A⟩∣A is an NFA and L(A)={0,1}∗} decidable? decidable?


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?


Solution

  • 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 :

    1. Construct DFA D_A equivalent to A
    2. Construct DFA D_0 that accepts {0,1}*
    3. Simulate decider F for EQ_DFA on where EQ_{DFA} = { | A and B are DFAs and L(A)=L(B)} (we know that EQ_{DFA} is a decidable language).
    4. Accept if F accepts; reject if F rejects."