reverse (x): get the reverse of a string x.

For instance; reverse (aaabc) = cbaaa

Ok, so I made this.

$W_1 ∈ Σ$* and $W_2 ∈ Σ$* and $x ∈ Σ$

I guessed that $W_1$.$(W_2x)$ is a concatenation then $(W_2x)$.$W_1$ is the reverse. But I can't explain it.

Also, I made an alternative resolution which is:

Being $W_x$ and $W_x$ two strings and $x$ the first letter of each string.

if $W_x = W_y$ $and$ $xW_x = W_yx$ then the string will be the reverse.

Is it right?

## Best Answer

Although ist is not completely clear to me what your question is, I will try to answer it. It seems you are looking for a way to recursively define a function to compute the reverse of a string.

One way can be based on the following equality: $$reverse(uv) = reverse(v)\cdot reverse(u)$$ You split your string at an arbitrary position and use recursion on both parts until you hit the end with $reverse(a) = a$ for all $a\in \Sigma$.

Your attempts with one of the parts of the string being only one symbol hide the fact that in general both parts need to be reversed. But if you want to have only one path of recursion you can do the splitting of the string always into the first or last symbol and the rest like in $$reverse(aw) = reverse(w)\cdot reverse(a) = reverse(w)\cdot a$$ for $a\in \Sigma$ and $w\in \Sigma^+$.

In the second part of your question, if $W_x$ and $W_y$ are equal and both start with $a$, then $aW_x=W_ya=W_xa$ means that for all relevant $i$ the $i$-th letter of $W_x$ is equal to the $i+1$st and consequently this can only be true for strings consisting only of $a$. All of these, of course, are equal to their own reverse.