I know a recursive definition is a function or procedure that is defined in terms of itself, for instance $f(n) = f(n - 1) + n$ or $f(n + 1) = f(n) + n + 1$. This makes sense to me in terms of numerical expressions, but with strings it starts to get a little confusing for me.

The problem I have is this: Construct a recursive definition for $f(x) = xy$, where $y$ is the reverse of $x$ for strings over the alphabet $\{ a, b \}$.

I guess I start getting confused when it says y is the reverse of x.

So what I am thinking is that we have this:

$f(\Lambda) = \Lambda$, $f(xa) = af(x)$, $f(xb) = bf(x)$.

But them I am confused on where $y$ goes. Any ideas on what I am doing wrong?


1 Answer 1


First of all, let me recall the definition of the reverse. If $x = a_1a_2 \dotsm a_n$, then the reverse of $x$ is the word $\tilde x = a_n \cdots a_2a_1$. Note that I am using the notation $\tilde x$ instead of $y$ to remember that it depends on $x$. You will see why this is important below.

Thus, by definition $f(x) = x\tilde x$. If $1$ denotes the empty word, we have $f(1) = 1$. Next, you tried to compute $f(xa)$, where $a$ is a letter, but you made a mistake. In fact, $f(xa) = xa\widetilde{xa} = xaa\tilde x$, which does not help much to get a recursive definition.

Let's try instead to compute $f(ax)$. Then we get $f(ax) = ax\widetilde{ax} = ax\tilde xa = af(x)a$, which gives the required recursive definition. Let us compute for instance $f(abb)$ to check whether our recursive definition works. We get successively $$ f(abb) = af(bb)a = abf(b)ba = abbf(1)bba = abb1bba = abbbba = abb\widetilde{abb} $$ It looks good!

  • 1
    $\begingroup$ Great answer, I wish I could give you more than one upvote. I just have one small hint to add for the OP: when constructing recursive definitions, it is often a good idea to start with the smallest or base case, which in your case is the empty string. $\endgroup$
    – mrp
    Mar 24, 2015 at 21:45
  • $\begingroup$ @mrp I fully agree with your hint on the base case and I thank you for your kind words. $\endgroup$
    – J.-E. Pin
    Mar 24, 2015 at 23:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .