Question

If s is a string, define its reverse s^R as follows.\begin{array}{|c|c|}\hline B. & \lambda^R = \lambda \\ \hline R. &

Discrete math

If s is a string, define its reverse $$s^R$$ as follows.
$$\begin{array}{|c|c|}\hline B. & \lambda^R = \lambda \\ \hline R. & \text{If s has one or more symbols, write} \\ & s = ra \\ & \text{where a is a symbol and r is a string (possibly empty). Then} \\ & s^R = (ra)^R = ar^R. \\ \hline \end{array}$$
Compute $$(cubs)^R$$. Justify each step using the definition.

2021-05-17
Here, we need to compute the reverse of a stringusing the given definition of R and B. R is the recursive definition in which the last symbol is made the first symbol and R is applied on the rest of the string. The base case here that of the empty symbol i.e $$\lambda$$ which is given in part B.
1. In the first step, R is applied on "cubs" which makes the symbol "s" to be the first symbol and then recursively R will be applied on "cub"
2. Similar to step 1, R is applied on "cub" and after "s", the next symbol will be "b" i.e. "sb" . R will now be applied on "cu"
3. Again, after applying R on "cu" , we get the next symbol to be "u" i.e "sbu". R will now be applied on "c".
4. Since, "c" is the last symbol, an empty string symbol is inserted before "c" so that R can be applied. This makes it "$$\lambda$$c". Now R will be applied on this.
5. After applying R, we get "c" to be the next symbol i.e. "sbuc". Now we are left with $$\lambda$$.
6. Apply part B on $$\lambda$$ which will give $$\lambda$$ again.
7. Since $$\lambda$$ is the empty string, it can be removed. Therefore, remove it. The reversed string becomes. "sbuc".
$$cubs^R$$
$$= s(cub)^R$$
$$= sb(cu)^R$$
$$= sbu(c)^R$$
$$= sbu(\lambda c)^R$$
$$= sbuc(\lambda)^R$$
$$= sbuc(\lambda$$
$$= sbuc$$