I only need problem 3 answered.

/ d www.cse.uconn.edu/-dgoldin/cse3502/hwk2.html ::: Apps UCONN Libraries D MyHomer D Ask a Librarian WorldCat m My Courses-Blackboard Lea E CSE 3502 Home Page, Fall 20 x y E cSE 237, Homework 1 Fall 2 D Introduction to the Theory of x X Reworks-HuskyCT D SkyBo( Student Admin CSE 3502, Homework 2: Finite State Automata due Tuesday 2/6/17 at the beginning of class Please hand in the homework ON PAPER, either handwritten or printed. Note: in this homework, we are looking for proper proofs, with steps, making use of definitions and building on what's given. Please refer to the book for examples of proper proofs. Problem 1. a) Let L be all strings over (0, 1 that contain a pair of I's separated by an odd number of symbols. Draw the diagram of an NFA with 4 states that accepts L b) Let L be the language w: w contains an even number of O's, or contains exactly two 1's). Draw the diagram of an NFA with 6 states that accepts L. Hint: To "debug" your NFA, look for strings it accepts but should not, or strings it does not accept but should. Problem 2. Compliment (a) Let M be some DFA s, d g F We create a DFA M" by swapping he accept and ect states o M so t a M ( S d 90 2-A Prove that L st eco plemer ofcak t s r s u (b) Suppose that in (a) above M were not a DFA but an NFA. Is it still true that, if we create Mas above, then L(M) is the complement of L(M)? Plcase prove that it is not, by finding a counterexample. Problem 3. Reversal Given a language L, we define Rev(L), the reverse of L as freversc(w), for all w in L) (for example, Rev(f"abc", "cb"I) is "cba", "bc"]). Prove by induction on the structure of regular expressions that ifL is regular (meaning, t can be represented by a regular expression), then Rev(L) is also regular In your proof, you can make use of the following facts about languages without having to prove them: Rev(L1 U L2)Rev(L) U Rev(L2) Rev(Ll o L2)-Rev(L2)" Rev(LI) Rev(L) (Rev(L)* Hint: start by formulating very carefully what exactly is the claim that you will be proving about all regular expressions