For any string x define xR to be that same string reversed T

For any string x, define x^R to be that same string reversed. The intuition is plain enough, but to support proofs we\'ll need a formal definition: epsilon^R = epsilon (ax)^R = x^R a, for any symbol a and string x We\'ll use the same notation to denote the set formed by reversing every string in a language: A^R = {x^R I x Element A} Using these definitions, prove the following properties of reversal: Prove that for any strings x and y, (xy)^R = y^Rx^R. Prove that for any string xy (x^R)^R = x. Prove that for any languages A and B, (A Union B)^R = A^R Union B^R.

Solution

a)Inductive Step: Assume that (xy)^r = y^rx^r holds for an arbitrary string y. --- Induction Hypothesis
We are going to show that (x(ya))^r = (ya) ^rx^r holds for any symbol a in .
(x(ya))^r = ((xy)a)^r by the associativity of concatenation
= a(xy)^r by the definition of reversal
= a(y^rx^r) by the induction hypothesis.
= (ay^r)x^r by the associativity of concatenation
= (ya)^rx^r by the definition of reversal

Thus (xy)^r = y^rx^r for any strings x and y.

b)Induction hypothesis: if 0 |x| n, then (x ^R) ^R = x. Induction step: Suppose |w| = n + 1. Then we can write w = xa, where a is a symbol and 0 |x| n.

Then (w ^R) R = ((xa) ^R) ^R since w = xa = (ax^R) ^R since (xy) ^R = y ^Rx ^R (use inner R and think of a as a string of length 1) = (x ^R) ^Ra ^R same as previous line but using outer R = (x ^R)a = xa = w since w = xa (by the induction hypothesis).

3)For a string x=x1x2…xn, x^R   =xn…x2x1,For a language A, A^R= {x^R | x A},Show that if A is regular, so is A.

Proof.

(1)     ^R=          is regular.

(2) For any symbol a, {a}^R = {a} is regular.

(3) Suppose that for regular languages A and B, A^R   and B^R are regular. Then

   (A U B)^R   = A^R U B^R    is regular,

   (AB)^R = B^R A^R   is regular.

    (A*)^R   = (A^R )* is regular.