a. Definition: The reverse of a string u, denoted uR, is defined recursively as follows: (1) = (Note that is the empty string.) (2) For any character a, and any string w, then (wa)R -awR This definition, in words, is on page 14. Claim: (uv)R-vRuR for any strings u and v Proof. By structural induction on v. Base case: E. Let u be any string (ue)R- Induction step: Let v be an arbitrary string. Assume that for all strings u, (uv)-vRuR. We need to show that, for each character a and all strings u, (u v)(va)RuR By the recursive definition of reverse: (u va)R By the inductive hypothesis: (uv)R Also, by the recursive definition of reverse: (va)R Thus, (u va)R def (IH) (def) (va)RuR