3
$\begingroup$

It is known that when NFA's accepting states are swapped with rejecting states, the recognized language is not complement of the original language. For some language, it may be the case that some strings that were recognized in the original NFA may still be recognized in the state-swapped NFA.

My question is, is there a language $L$ that in the original NFA a string is not recognized(rejected), but in the NFA where accepting states become rejecting states and rejecting states become accepting states the string is also rejected?

Improve this question
$\endgroup$
1
  • $\begingroup$ This is maybe too far off for you, but you are after the reason for why the "flip states" technique does not work für Büchi automata. $\endgroup$
    – Raphael ♦
    Feb 6, 2015 at 13:42

2 Answers 2

Reset to default
3
$\begingroup$

Yes, there is such a situation. A string is rejected when there is no computation for that string at all. Obviously there will be no computation after swapping accepting states.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Technically correct, but I think the whole "flip states" idea assumes the automaton to be complete, doesn't it? $\endgroup$
    – Raphael ♦
    Feb 6, 2015 at 13:43
  • $\begingroup$ @Raphael In my opinion the "flip states" technique assumes determinism, exactly one transition for each letter in each state. The question states what may go wrong when there are too much paths. Here is the dual, what goes wrong when there is no path. I believe these are opposite sides of the same coin. $\endgroup$
    – Hendrik Jan
    Feb 6, 2015 at 13:47
  • $\begingroup$ I don't think determinism is needed, technically. The OP will have to decide whether your answer is relevant (to them) or a pathological corner case. $\endgroup$
    – Raphael ♦
    Feb 6, 2015 at 14:49
3
$\begingroup$

It depends on whether the NFA contains a path for every possible word.

If there is an input word where there is no path through the NFA at all labelled with that word, then yes, this can happen. See Hendrik Jan's answer.

On the other hand, it is often assumed that the automaton is complete: that for every possible input word, there is at least one path in the automaton labelled with that word. (For instance, this can be arranged by ensuring that for every state $q$ and every possible input letter $x \in \Sigma$, there is a transition out of $q$ labelled with $x$.) If you assume the automaton is complete, the answer is: No.

In particular, if the automaton is complete, the answer is: No, the magic of nondeterminism is that if there's any valid computation path that will end in an accept state, the string is accepted. In this case, all possible computation paths in the original NFA led to rejection (had there been any valid path the string would be accepted, so they must all reject), so in the inverted NFA, they all lead to acceptance.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ That is assuming there is a path for every word (hence Hendrik Jan's answer). $\endgroup$
    – Klaus Draeger
    Feb 6, 2015 at 13:41
  • $\begingroup$ @KlausDraeger Technically correct, but I think the whole "flip states" idea assumes the automaton to be complete, doesn't it? $\endgroup$
    – Raphael ♦
    Feb 6, 2015 at 13:43
  • $\begingroup$ @Raphael I'm not sure if that is necessarily assumed. It is a natural condition though, and it does ensure that at least one of the NFA accepts any given word. $\endgroup$
    – Klaus Draeger
    Feb 6, 2015 at 13:47
  • 1
    $\begingroup$ On second thought, Luke, things go horribly wrong if some computations accept and others don't (the typical case): those are also accepted by the flipped automaton. We need for every input that either all or no computation accepts; only then can we flip. (cc @KlausDraeger) $\endgroup$
    – Raphael ♦
    Feb 6, 2015 at 14:47
  • $\begingroup$ See also here. $\endgroup$
    – Raphael ♦
    Feb 10, 2015 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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