3
$\begingroup$

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!

$\endgroup$
5
  • 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
    Commented Feb 1, 2016 at 14:17
  • $\begingroup$ Thank you! I worked it though and I came up with an example now :) $\endgroup$ Commented Feb 1, 2016 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$ Commented Feb 1, 2016 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
    Commented Feb 1, 2016 at 14:35
  • $\begingroup$ I wish I could upvote all of you, thank you! $\endgroup$ Commented Feb 1, 2016 at 14:42

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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