This question is from Theory of Computation

Please show your work with clear and legible work.

- = = You are given 2 NFAs N1 = (Q1, 2, 81, 910, Fi) and N2 = (Q2, 2, 82, 220, F2). Con- E struct an NFA N = (Q, 2,8,90, F) recognizing L(Ni) \L(N2). Recall that the set difference is defined by A | B = {ele A and e&B}. One solution would be to find DFAs equivalent to Ni and N2, followed by known constructions for DFAs recognizing the complement and the intersection of regular languages. If |Q1] = k and Q2] = k2 then you would actually obtain a DFA with up to 2k+k2 states recognizing L(Ni)\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 a (a) Find a solution N with much fewer states 2ki+k2 (assuming k is large). (b) How many states has your NFA N? - = = You are given 2 NFAs N1 = (Q1, 2, 81, 910, Fi) and N2 = (Q2, 2, 82, 220, F2). Con- E struct an NFA N = (Q, 2,8,90, F) recognizing L(Ni) \L(N2). Recall that the set difference is defined by A | B = {ele A and e&B}. One solution would be to find DFAs equivalent to Ni and N2, followed by known constructions for DFAs recognizing the complement and the intersection of regular languages. If |Q1] = k and Q2] = k2 then you would actually obtain a DFA with up to 2k+k2 states recognizing L(Ni)\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 a (a) Find a solution N with much fewer states 2ki+k2 (assuming k is large). (b) How many states has your NFA N