![3. [5pt] Provide an example of an NFA N with the property that swapping its accept and nonaccepting states does not yield an NFA N that recognizes the complement of L(N) Hint: In group exercise 2 you will prove that given a DFA M that accepts a language L(M) C Σ, you can swap the accept and nonaccepting states in M to yield a new recognizing the complen](https://d2vlcm61l7u1fs.cloudfront.net/media%2F178%2F1786bafd-0ac7-493c-befb-a6cf0df8daf8%2FphpgxMsyV.png)
Provide an example of an NFA N with the property that swapping its accept and nonaccepting states does not yield an NFA N’ that recognizes the complement of L(N).
(Solved Homework): Provide an example of an NFA N with the property that swapping its accept and nonaccepting states does not yield an NFA N' that recognizes the complement of L(N)….
Expert Answer
Don't use plagiarized sources. Get Your Custom Essay on
(Solved Homework): Provide an example of an NFA N with the property that swapping its accept and nonaccepting states does not yield an NFA N' that recognizes the complement of L(N)….
Get an essay WRITTEN FOR YOU, Plagiarism free, and by an EXPERT!
Solution:
So, we have an example here
An NFA accepting the language L(M)= {w*, w ends with 00}
Now let’s see the NFA which accepts this language then we will complement it.
Now, let’s complement it by changing the accepting state to non-accepting and non-accepting to accepting state.
So the language which should be accepted here is
An NFA accepting the language L(M)= {w*, w does not end with 00}
After running input string 100 we can see that NFA is accepting the string
So here we can see that after complementing this NFA we are not getting the complemented language. However, we can get this right if we have a DFA and then complement it.
