Prove that for any strings x and y, (xy)R = yRxR. Hint: Use induction on |x|. For any string x, define xR to be that same string reversed. The intuition is plain enough, but to support proofs well need a formal definition:

^R = (ax)^R = x^Ra, for any symbol a and string x

Well use the same notation to denote the set formed by reversing every string in a language:

A^R = {x^R | x A}

Using these definitions, prove the following properties of reversal:

(a) Prove that for any strings x and y, (xy)R = yRxR. Hint: Use induction on |x|. When doing induction you'll want to use x = az, rather than x = za (where z is a string, and "a" is a single character)

(b) Prove that for any languages A and B, (AB)^R = B^RA^R. Youll need the result from Part a. Hint: DO NOT USE INDUCTION! Just do a regular old proof, using the definition of set concatenation: AB = {xy|x A y B}

(c) Prove that the regular languages are closed for reversal. Hint: Using structural induction, show that for every regular expression r, there is a regular expression r' with L(r' ) = (L(r))^R. Remember to treat a-b as proven. Most of the work has been done at this point.