Nondeterministic Finite Automata 4. For the following language: L = {x | x is a binary string that has 1101 or 1100 or 0001 as a substring} (a) (7 points) Design an NFA for L using the method discussed in class. (b) (7 points) Remove all -transitions from your NFA. (present an equivalent NFA with no -transitions.)

5. (Bonus) Consider the NFA N. (a) (5 points (bonus)) Show that if N recognizes the language A, swapping the accept and non-accept states in N does not necessarily yield an NFA that recognizes the A. (b) (5 points (bonus)) Is the class of languages recognized by NFAs closed under complement? Explain your answer.