I realized that if a language L is recognized by a DFA, then flipping its accept and reject states (aka switching all the accept to reject states and all the reject states to accept) works to recognize the complement of L (which wold be L^c).

I was curious if that worked also with NFAs (flipping the accept and reject states to go from L to L complement), but with their additional paths it doesn't seem like it would work..Definitely seems like it would have too many accept states that aren't correct.

Is this correct? Is there more to it? Thank you!

  • 1
    $\begingroup$ You're right. Flipping the states doesn't work in nondeterministic machines (and automata in particular). Try to think of an example! (hint: there is an example with two states) $\endgroup$ – Shaull Feb 1 '16 at 14:17
  • $\begingroup$ Thank you! I worked it though and I came up with an example now :) $\endgroup$ – user3295674 Feb 1 '16 at 14:23
  • $\begingroup$ Indeed. In fact it is "twice wrong" for nondeterministic machines. By this I mean that (1) there might be strings accepted both by the machine and by its flipped version, and (2) at the same time there might be strings accepted by neither of them. $\endgroup$ – Hendrik Jan Feb 1 '16 at 14:25
  • 1
    $\begingroup$ Note that flipping the states does provide one direction of the containments: if $A$ is an NFA, and $B$ is the "flipped" NFA, then $\overline{L(A)}\subseteq L(B)$. That is, $B$ accepts everything that $A$ doesn't, but might accept additional strings (assuming $A$ is complete - every word has at least one run). $\endgroup$ – Shaull Feb 1 '16 at 14:35
  • $\begingroup$ I wish I could upvote all of you, thank you! $\endgroup$ – user3295674 Feb 1 '16 at 14:42

Same thing does not hold for an NFA. Example

q0 -> 0 -> q1
q0 -> 0 -> q2

q0 is the start state, q1 is the final state.

| cite | improve this answer | |

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