= [20 + 5=25 points] You are given 2 NFAs Ni = (Q1, , 81,910, F1) and N2 = (Q2, 2, 82, 920, F2). Con- struct an NFA N = (Q, 8, 8,90,F) recognizing L(Ni) \L(N2). Recall that the set difference is defined by A B = {ele e A and e& B}. One solution would be to find DFAs equivalent to N, and N2, followed by known constructions for DFAs recognizing the complement and the intersection of regular languages. If Q1] = ky and Q2 = k2 then you would actually obtain a DFA with up to 2k1+k2 states recognizing L(N)\L(N2). Naturally, this DFA can be viewed as an NFA with the same number of states. However, as we only want an NFA (not a DFA), we can be much more efficient. Hint: The construction for the intersection works with NFA's just as well as with DFA's. (a) Find a solution N with much fewer states 2k+k2 (assuming k is large). (b) How many states has your NFA N? a = [20 + 5=25 points] You are given 2 NFAs Ni = (Q1, , 81,910, F1) and N2 = (Q2, 2, 82, 920, F2). Con- struct an NFA N = (Q, 8, 8,90,F) recognizing L(Ni) \L(N2). Recall that the set difference is defined by A B = {ele e A and e& B}. One solution would be to find DFAs equivalent to N, and N2, followed by known constructions for DFAs recognizing the complement and the intersection of regular languages. If Q1] = ky and Q2 = k2 then you would actually obtain a DFA with up to 2k1+k2 states recognizing L(N)\L(N2). Naturally, this DFA can be viewed as an NFA with the same number of states. However, as we only want an NFA (not a DFA), we can be much more efficient. Hint: The construction for the intersection works with NFA's just as well as with DFA's. (a) Find a solution N with much fewer states 2k+k2 (assuming k is large). (b) How many states has your NFA N? a