Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am having difficulty understanding the recursive definition of a language. The problem asked how to write this non recursively. But I want to understand just how a recursive definition of a language works.

Recursive definition of a subset of L of $\{a,b\}^*$.

Basis : $a\in L$

Recursive Definition : for any $x\in L$, $ax$ and $xb$ are in $L$.

Below is my attempt at explaining the recursive definition.

Starting with the basis $a$ saying that $ax$ is in it means that all strings formed such as $\{a,aa,aaa,...\}$ are present.

Defining all $xb$ represents $\{ab,abb,abbbb,...\}$

The answer I have so far is $\{a\}^*\{b\}^*$ but again it is understanding it that I am after.

share|cite|improve this question
You forgot the $a$ in the middle. The expression that you produced allows $bbb$ to be in $L$. Informally, the words in $L$ have a positive number of $a$ followed by any number of $b$, including $0$. – André Nicolas Jan 27 '13 at 21:06
up vote 3 down vote accepted

Pretend you're a computer.

Step 0. You start with $\{ a \}$.

Apply the recursive definitions to each word you have so far. This gives you $aa$ and $ab$, so add them to your list.

Step 1. You now have $\{ a, aa, ab \}$.

Applying the recursion again to each word gives you $aa,ab,aaa,aab,aab,abb$. There's some duplication going on here, but that doesn't matter.

Step 2. You now have $\{ a, aa, ab, aaa, aab, abb \}$.

Do it again. This gives you $$aa,ab,aaa,aab,aab,abb,aaaa,aaab,aaab,aabb,aabb,abbb$$ so append these to your list, ignoring duplicates as before.

Step 3. You now have $\{ a,aa,ab,aaa,aab,abb,aaaa,aaab,aabb,abbb \}$.

Do you see a pattern emerging? Try and guess the general form of a word in this language and then prove by induction on the 'step' above (a.k.a. structural induction) that your guess is correct.

share|cite|improve this answer
           /               \
         aa                 ab
    /        \           /       \
  aaa       aab        aab       abb
 /   \     /   \      /  \      /   \
aaaa aaab aaab aabb aaab aabb aabb abbb
share|cite|improve this answer

The recursive definition says that once you have a word of $L$, you can prefix an $a$ or suffix a $b$ to get another word of $L$. You can repeat either of these operations any number of times, so you can prefix $a^n$ for any $n\ge 0$ or suffix $b^n$ for any $n\ge 0$, or both (not necessarily with the same $n$). If you start with the one given word $a$, and apply the ‘prefix $a$’ operation $m$ times and the ‘suffix $b$’ operation $n$ times, you get $a^{m+1}b^n$. (The order in which you perform the $m+n$ operations pretty clearly doesn’t matter.) Since the definition doesn’t allow you to do anything else, these are the only words that you can form:

$$L=\{a^{m+1}b^n:m,n\ge 0\}\;.$$

In other words, you can have any positive number of $a$’s followed by any non-negative number of $b$’s. A regular expression describing this language is $aa^*b^*$; the first $a$ ensures that you get at least one $a$. (An extended regular expression equivalent to this is $a^+b^*$, if you’ve been introduced to the notation $a^+$; it’s just an abbreviation for $aa^*$.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.