Peter Linz Edition 4 Exercise 1.2 Question 2 (Page No. 27)

Question

The reverse of a string can be defined more precisely by the recursive rules

$a^R=a$,

$(wa)^R=aw^R$, for all $a∈Σ$, $w∈Σ^*$.

Use this to prove that$(uv)^R=v^Ru^R$, for all $u,v∈Σ^+$.

Answer 1

$(uv)^R = v^Ru^R,$ for all strings $u,v.$

If $u = \epsilon,$ then $u^R = \epsilon$ and hence $(uv)^R = v^R = v^Ru^R.$

If $v = \epsilon,$ then $v^R = \epsilon$ and hence $(uv)^R = u^R = v^Ru^R.$

Now, suppose $u = u_1u_2 \dots u_m$ and $v = v_1v_2 \dots v_n$, with $m,n \geq 1.$

Then, $(uv)^R = (u_1u_2 \dots u_mv_1v_2 \dots v_n)^R = v_n \dots v_2v_1x_m \dots x_2x_1 = v^Ru^R.$

Detailed Video Solution