Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be…

Key insight: after swapping accepting and non-accepting states in this NFA, every string over {0,1} has a nondeterministic run that ends in an accepting state.

Why every string is accepted (case analysis):

• Empty string: the start state was non-accepting in the original machine, so it becomes accepting in the modified machine. Hence the empty string is accepted.

• Strings beginning with 0: from the start state there is a transition on 0 to the left state. The left state is accepting in the modified machine and has self-loops on both 0 and 1, so it can consume the remainder of the input and accept.

• Strings beginning with 1: from the start state there is a transition on 1 into the top state, and from that top state there are transitions on the next input symbol that reach one of the now-accepting states (start or left). Once such an accepting state is reached it can loop to consume the rest of the input. Therefore any longer string starting with 1 can be guided into an accepting state.

• Single-symbol string "1": although one run reading the single 1 may end in the former accepting (now non-accepting) top state, nondeterminism allows choosing a run that reaches an accepting state (for example, by moving so that the remainder of the computation ends in the start or left state). Thus the single-symbol string is also accepted.

Conclusion: for every w in {0,1}* there exists at least one accepting run in the modified NFA, so the language accepted after swapping final and non-final states is the entire set {0,1}*.