How to use general recursion to generate a set of words?

Question

I am just getting to recursion in one of my classes, and I'm a bit confused on how to go about generating a set of words and the notation.

Given the following question, how would I go about generating this set?

(assuming ∑={a,b}), the set of strings with twice as many a’s as b’s.

If I start by saying that λ∈T as my base case, how would I then generate the recursive case?

Answer 1

Edit: Please consider accepting @Brian M. Scott's answer as it is complete and more rigorous.

---

(Too large for a comment, but I hope it will give you some insight.)

Generate 2 $a$'s for each $b$. First, you have 3 possibilities ($1^{st}$ generation). $$ \mathbf{w}_1^1=aab, \ \mathbf{w}_2^1 = aba, \ \mathbf{w}_3^1=baa $$ Next, generate all the possible permutations of each previous $\mathbf{w}_i^1$, inserting each previous $\mathbf{w}_i^1$ at each possible place ($2^{nd}$ generation). For example: $$ \mathbf{w}_1^2 = aab|\mathbf{w}_1^1, \hspace{10pt} \mathbf{w}_2^2 = aba|\mathbf{w}_1^1, \hspace{10pt} \mathbf{w}_3^2 = baa|\mathbf{w}_1^1 \\ \mathbf{w}_4^2 = aa|\mathbf{w}_1^1|b, \hspace{10pt} \mathbf{w}_5^2 = ab|\mathbf{w}_1^1|a, \hspace{10pt} \mathbf{w}_6^2 = ba|\mathbf{w}_1^1|a \\ \large \dots $$

Note that you can insert multiple (previous) strings at different positions, for the next generation. You can go to the next generation only after you have enumerated all possible strings for the current generation, and this includes inserting multiple previous strings.

I have used the notation $u \ | \ v$ to denote the concatenation of $u$ and $v$, and $\mathbf{w}_i^j$ denotes the $i$-th word in generation $j$.

You can then derive a recursive formula for $\mathbf{w}_i^j$ using this.

Answer 2

I would also include in the base case the three minimal non-empty strings in $T$:

• $\lambda,aab,aba,baa\in T$
• If $u,v\in T$, and $v=xy$, then $xuy\in T$. (Note that $x$ or $y$ can be empty.)

The hard part is going to be proving that this actually generates all of $T$; this will be the case if and only if every $u\in T\setminus\{\lambda,aab,aba,baa\}$ has a proper substring in $T$. (Why?)

HINT: Set $c_0=0$, and for $k=1,\ldots,n$ let

$$x_k=\begin{cases} c_{k-1}+1,&\text{if }x_k=a\\ c_{k-1}-2,&\text{if }x_k=b\;; \end{cases}$$

note that $c_n=0$, since $u\in T$.

• Show that if $c_k=0$ for some $k\in\{1,\ldots,n-1\}$, $u$ has a proper substring in $T$.
• Suppose that $c_i>0$ for $i=1,\ldots,n-1$, and let $c_k=\max\{c_i:0\le i\le n\}$. Show that there are $i,j$ such that $0<i<k<j<n$ and $c_i=c_j$ and conclude that $u$ has a proper substring in $T$. (Use the fact that although it decreases by $2$ when it decreases, the counter $c$ only ever increases by $1$. Thus, it can skip over a value when decreasing but not when increasing.)
• Prove a similar result in the case that $c_i<0$ for $i=1,\ldots,n-1$.
• Show that the only remaining possibility is that $c_k=c_{n-1}=-1$ for some $k$ such that $2\le k<n-1$ and again conclude that $u$ has a proper substring in $T$.

It may help to realize that these bullet points correspond to the following types of strings, respectively:

• $u=vw$ for some non-empty $v,w\in T$.
• Every non-empty proper initial segment of $u$ has too many $a$s to be in $T$.
• Every non-empty proper initial segment of $u$ has too many $b$s to be in $T$.
• $u$ has the form $xva$, where $xa,v\in T$, every non-empty proper initial segment of $x$ has too many $a$s, $x$ ends in $b$, and $x\notin T$.