patternMinor
When states that are not accepting states become accepting states in NFA, what happens?
Viewed 0 times
nfawhatarestatesthatacceptingwhenhappensnotbecome
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#38041, answer score: 3
Revisions (0)
No revisions yet.