Understanding recursive definitions of a language.

Question

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.

Answer 1

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.

Answer 2

                   a
           /               \
         aa                 ab
    /        \           /       \
  aaa       aab        aab       abb
 /   \     /   \      /  \      /   \
aaaa aaab aaab aabb aaab aabb aabb abbb

Answer 3

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^*$.)