3. Think about, but do not hand in: A DFA or NFA can, in general, have zero, one, or many accept states. Show that every NFA can be converted into another NFA recognizing the same language, but which has exactly one accept state. (This is solved exercise 1.11 in Sipser if you'd like to check your solution.) To hand in: Prove that this is not true for DFAs. That is, show that there is a regular language L such that every DFA recognizing L requires at least two accept states. Hint: If L contains the empty string, what can you say about the start state of any DFA recognizing L? 3. Think about, but do not hand in: A DFA or NFA can, in general, have zero, one, or many accept states. Show that every NFA can be converted into another NFA recognizing the same language, but which has exactly one accept state. (This is solved exercise 1.11 in Sipser if you'd like to check your solution.) To hand in: Prove that this is not true for DFAs. That is, show that there is a regular language L such that every DFA recognizing L requires at least two accept states. Hint: If L contains the empty string, what can you say about the start state of any DFA recognizing L