I am having a really hard time working the problem below out.
I am not sure I am even on the right direction with this logic . Swapping the accept and reject states alone is not sufficient to accept all string of the language ~ L. We would need to swap the transition directions as well for L (with the bar on top) to be accepted.
If I am not mistaken L with the bar on top is simply not L (~L), right?
As an example, I created an NFA that accepts any string that has at least two zeros. Swapping the accept states with the reject states, didn't really help me prove anything by counterexample.
This is the problem:
Your friend thinks that swapping accept and reject states of an NFA that accepts a language L, that the resulting NFA must accept the language L (with a bar on top). Prove by counter-example, that your friend is incorrect.
Best Answer
$\bar L$ is the complement of $L$, that is, $\bar L$ is the set of strings that are not in $L$.
Hint: make a nondeterministic automaton that accepts every string, and so that if you switch the accepting and rejecting states it still accepts every string.