1. Suppose the languages recognized by DFAs M and N are L1 and L2 respectively. How can
we use DFAs M and N to construct a DFA that recognizes the language L1ˆ©L2? [Can you
use De Morgan’s Law?]
2. Show by giving an example that, if M is an NFA that recognizes language L, swapping the
final and non-final states in M doesn’t necessarily yield a new NFA that recognizes the
complement of L. Is the class of languages recognized by NFAs closed under
complement? Explain your answer.