For DFAs, swapping the accept states produces a machine which recognizes the complement language. But this...

Transcribed Image Text:

For DFAs, swapping the accept states produces a machine which recognizes the complement language. But this is not always true for NFAs. a) Find an NFA M for which swapping accept states produces an NFA N where the com- plement of L(M) is not L(N). Describe L(N) and L(M). b) Given your counterexample, is the class of languages recognized by NFAs closed under complement? Explain. For DFAs, swapping the accept states produces a machine which recognizes the complement language. But this is not always true for NFAs. a) Find an NFA M for which swapping accept states produces an NFA N where the com- plement of L(M) is not L(N). Describe L(N) and L(M). b) Given your counterexample, is the class of languages recognized by NFAs closed under complement? Explain.