Why does this proof of reverse of string is correct?

452 Views Asked by At

Solution

Given that $a^R=a$, $$(wa)^R=aw^R\;.$$ Now we have to prove $(uv)^R=v^Ru^R$.

Let us assume that $u=wb$ and $v=wa$.

$$\begin{align*} LHS=(uv)^R=(wbwa)^R&=bw^R\cdot aw^R\;\color{red}\Leftarrow\\ &=(bw^R)(aw^R)\\ &=(bw)^R(aw)^R\\ &=v^R\cdot u^R=RHS \end{align*}$$

Hence proved

(Original screenshot)

It is a proof for reverse of string, $a\in\Sigma$ and $w\in\Sigma^*$

Isn't the part I marked with an arrow incorrect?

Isn't it supposed to be: $aw^R\cdot bw^R$ ?

The key part that I don't understand:

\begin{align}LHS=(uv)^R=\color{red}{(wbwa)^R} &\,\color{red}{=bw^R\cdot aw^R}\\ &=(bw^R)(aw^R)\\ &=(bw)^R(aw)^R\\ &=v^R \cdot u^R=RHS \end{align}

1

There are 1 best solutions below

0
On

As written in the comments, the "solution" is messed up at several places.

1) What you noticed, in general we have $(wbwa)^R \ne bw^R \cdot aw^R$.

2) The assumption that $u$ and $v$ have a common prefix $w$ seems strange to me, in general we can just suppose that $u = wb$ and $v = w'a$ with $w,w' \in X^{\ast}, a,b \in X$.

3) The third and fourth line seem to be wrong, in general $(bw^R)(aw^R) \ne (bw)^R(aw)^R$.

4) In the last line he seems to replace $bw$ by $v$ and $aw$ by $u$, which is not consistent how $u$ and $v$ where choosen.

The exercise asks you to prove that the mapping $u \mapsto u^R$ is an anti-homomorphism, but strangely in the wrong solution at 1) and 2) he seems to use the wrong assumption that it is a homomorphism, which it is not, i.e. in general we have $(u\cdot v)^R \ne u^R \cdot v^R$.

To give a correct solution, let $u,v \in X^{\ast}$. We do induction on the length of $v$. If $|v| \in \{0,1\}$ the equation clearly holds, in the case $|v| = 1$ by the inductive definition of the reverse operation. Now suppose $|v| > 1$, then $uv = uwx$ with $x \in X$ and by definition we have $$ (uv)^R = (uwx)^R = x(uw)^R $$ and by induction hypothesis applied to $|w| < |v|$ we have $(uw)^R = w^R u^R$, hence $$ (uv)^R = xw^R u^R. $$ And again, by definition $xw^R = (wx)^R$, hence $(uv)^R = (wx)^R u^R = v^R\cdot u^R$. $\square$