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

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?

Mathematics Asked by Pwelb on November 14, 2021

2 Answers

2 Answers

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

  • $lambda,aab,aba,baain T$
  • If $u,vin T$, and $v=xy$, then $xuyin 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 $uin Tsetminus{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 $uin T$.

  • Show that if $c_k=0$ for some $kin{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:0le ile 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 $2le 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,win 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,vin T$, every non-empty proper initial segment of $x$ has too many $a$s, $x$ ends in $b$, and $xnotin T$.

Answered by Brian M. Scott on November 14, 2021

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.

Answered by Alexandru Dinu on November 14, 2021

Add your own answers!

Related Questions

Using L’Hopital’s rule to find the limit of this function

1  Asked on January 18, 2021 by gregorystory16


The Cauchy-Crofton formula on a plane

1  Asked on January 18, 2021 by jalede-jale-uff-ne-jale


Galois group Abstract algebra

1  Asked on January 18, 2021 by user462999


Ask a Question

Get help from others!

© 2021 All rights reserved.