# Nondeterministic finite automaton proof

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.

-

## 1 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.

-
Thank you for the hint:) I will give it a try... wait a minute, if my NFA accepts every string, then wouldn't swapping the accept and reject states would cause my NFA to accept no strings? – Epsilon Jan 25 '13 at 1:14
Remember it is a nondeterministic machine. It can do more than one thing at a time. – Carl Mummert Jan 25 '13 at 1:24
I am trying to build my NFA keeping epsilon character and empty set in mind. – Epsilon Jan 25 '13 at 1:26
I GOT IT! ....I think. So since we are thinking in terms of NFA where more than one thing is possible. Assume NFA has 3 states. Start state q1, accept state q2 and reject state q3. Transition from q1 to q2 has an epsilon character and transition from q1 to q3 has an epsilon character. If we swap the accept and reject states, our nfa will STILL accept every string. What do you think? – Epsilon Jan 25 '13 at 1:36
Yes, that is what I had in mind. Any symbol in state q2 takes it back to q2, and any symbol in q3 takes it back to q3. If you want, you can also eliminate the epsilon by letting q1 transition to both q2 and q3 no matter what character is seen in state q1. – Carl Mummert Jan 25 '13 at 2:04