1 (10 points) Let S = {0,1}. Use the method discussed in class to construct an NFA where its language is expressed by the regular expression (0U 1)*1. Note that you must construct a series of NFAs step-by-step 2 (10 points) Let E = {0,1}. Use the method discussed in class to construct an NFA where its language is expressed by the regular expression (01*)*. Note that you must construct a series of NFAs step-by-step 3 (20 points) Perform the following: (a) (5 points) Draw a state diagram of a DFA that recognizes the language {w | w ends with 01} Note that your machine should have exactly 3 states and make sure that your start state is the state qo and your accept state is the state (2. (b) (5 points) From your state diagram in (a), convert it into a GNFA as discussed in class. Note that you do not need to remove any states yet. (c) (10 points) From your GNFA in (b), convert it into a regular expressing using the method discussed in class. Note that you must remove states qo, q1, and then 92 in that order. 4 (12 points) For each regular language A, give an example of a string s in the language A of length at least 5. Then show that the string can be divided into s = xyz that satisfies these three conditions: 1. xy'z E A for any i > 0 2. y > 0 3. |xy0} f. A = {ww | W {0, 1}*} g. A= {011 | > j} h. A = {a'bick | i =j+k} 6 (30 points) Use the pumping lemma to show that the following languages are not regular. a. Aj = {0in2n | n > 0} is not regular. b. A2 = {www | We {a, b}*} c. Az = {abi | j = i or j = 2i}