Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

$\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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.