Problem 1 In class, we showed that if M is a DFA that recognizes language A, swapping the accepting and nonaccepting states yields a new DFA recognizing the complement of A. We then concluded that the class of regular languages is closed under complement. a [10 points] Show, by giving an example, that if N is an NFA that recognizes language B, swapping the accepting and nonaccepting states in N does not nec- essarily yield a new NFA that recognizes the complement of B b. [5 points] Is the class of languages recognized by an NFA closed under comple- ment? Explain your answer Problem 2 [15 points] Prove that the class of regular languages is closed under inter- section. That is, show that if A and B are regular languages, then A B-(w E A and w E B is also regular. Problem 3 [20 points] Prove that the class of regular languages is closed under reverse. That is, show that if A is a regular language, then AR - {wR w E A is also regular (Hint: given a DFA M = (Q,..q0,F) that recognizes A, construct a new NFA = (Q, ,8.%-F') that recognizes AR.] Problem 1 In class, we showed that if M is a DFA that recognizes language A, swapping the accepting and nonaccepting states yields a new DFA recognizing the complement of A. We then concluded that the class of regular languages is closed under complement. a [10 points] Show, by giving an example, that if N is an NFA that recognizes language B, swapping the accepting and nonaccepting states in N does not nec- essarily yield a new NFA that recognizes the complement of B b. [5 points] Is the class of languages recognized by an NFA closed under comple- ment? Explain your answer Problem 2 [15 points] Prove that the class of regular languages is closed under inter- section. That is, show that if A and B are regular languages, then A B-(w E A and w E B is also regular. Problem 3 [20 points] Prove that the class of regular languages is closed under reverse. That is, show that if A is a regular language, then AR - {wR w E A is also regular (Hint: given a DFA M = (Q,..q0,F) that recognizes A, construct a new NFA = (Q, ,8.%-F') that recognizes AR.]