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!
Best Answer
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\ .$$