1. (15 pt) Let uw * be two strings over the alphabet .. Prove by induction that (uw) R = WRUR. (Note: the reverse of a string x is denoted as xR.) 2. (20 pt) Prove or disprove the following statements: (a) (@U*) n ( - (*)) = . (b) For every language L CE*, (L+)* = L*. 3. (15 pt) For every two languages L1, L2 C * and the reverse of a language L be defined as LR { * | w = ExR for some x E L}. Then, prove that (L1L2) R = LLR 4. (15 pt) Let S = + {a,b} be an alphabet. Design a DFA that accepts strings whose parts including only a's is of even length. For instance, strings aa and baabaaaa are accepted whereas strings aba and aaab are rejected. 5. (15 pt) Design an equivalent NFA for each of the following regular expressions: (a) (babb* + a)* (b) (a + ba)b + aa)* 6. (20 pt) Show that the following languages are not regular. (a) L = {a'bi | i = 2;}. (b) L = {w {a,b,c}* | w is a palindrome (i.e. w = wR)}