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!
No comments:
Post a Comment