Proof on String Reverse

Question

I'm having trouble with a proof on a string reversal if anyone could lend a hand.

Given the recursive definition of String Reverse, R:

• $\varepsilon^R = \varepsilon$

• $(ax)^R=x^Ra, for x\in\sum^*$

Prove that $(xa)^R=ax^R$

My first instinct was to use proof by induction.

(Base Case) $|x|=0, i.e. x=\varepsilon$

LHS: $(xa)^R=(\varepsilon a)^R=(a)^r=a$

RHS: $a\varepsilon^R=a\varepsilon=a$

So our base case holds.

(Inductive Hypothesis) Assume true for $|x|=k, k \ge 0$,

$(xa)^R=ax^R$

(Inductive Step)

This is where I am stuck, as I know I have to show for the k+1 case, I can not figure out where to go from here. Any help would be appreciated, thanks!

Answer 1

What you need is a recursive definition of a string - more accurately, you need the inductive case of the definition, as you already have the base case (the empty string). Then you substitute the inductive case form for 'x' in both sides of your hypothesis, and the result should (if done right) suggest how to complete the proof.

Answer 2

We shall prove the stronger statement $$(yx)^R=x^Ry^R$$ by induction on $|y|$. Note that for $a\in A$ we have $a^R=a$.

If $|y|=1$, i.e., $y=a\in A$, then $(yx)^R=(ax)^R=x^R a=x^Ry^R$.

Assume that the claim is true for all $y$ of length $n$, and that $y=a y'$ with $a\in A$ and $|y'|=n$ is of length $n+1$. Then we have $$(yx)^R=\bigl(a(y'x)\bigr)^R=(y'x)^Ra=x^R y'^R a=x^R(ay')^R=x^Ry^R\ .$$