How Do You Recursively Define a Set of Strings?

A set of strings cannot be determined from the phrase “recursively defined” alone: you also need its alphabet, starting strings, and construction rules. A recursive definition gives those ingredients so you can generate the set step by step and rule out strings that the rules cannot produce.

The parts of a recursive definition

A recursive definition of a set of strings typically has four parts:

1. Alphabet: the symbols allowed in the strings, such as $\{a,b\}$.
2. Basis: one or more strings that belong to the set initially. The empty string, written $\varepsilon$, is a common base case.
3. Recursive rule: a rule that says how to form new strings from strings already in the set.
4. Minimality clause: the set contains only the strings obtained from the basis by applying the rules finitely many times.

The last condition matters. Without it, the stated basis and rules merely imply that some strings belong; they do not prevent unrelated strings from being included too.

Worked example: strings with equally many a’s and b’s in order

Consider the set $S$ defined over the alphabet $\{a,b\}$ by:

• Basis: $\varepsilon\in S$.
• Rule: If $w\in S$, then $awb\in S$.
• Minimality: Nothing belongs to $S$ unless it can be obtained from $\varepsilon$ by finitely many uses of the rule.

Here, $awb$ means put an $a$ at the beginning of $w$ and a $b$ at the end. Apply the rule repeatedly:

$$\begin{aligned} \varepsilon &\in S,\\ a\varepsilon b=ab &\in S,\\ a(ab)b=aabb &\in S,\\ a(aabb)b=aaabbb &\in S. \end{aligned}$$

Thus the first few members are $\varepsilon$, $ab$, $aabb$, $aaabbb$, and so on. In set-builder notation, this is

$S=\{a^n b^n:n\text{ is an integer and }n\ge 0\}.$

The exponent $n=0$ gives the empty string. Each application of the rule increases the number of $a$’s and $b$’s by one, so every generated string has all its $a$’s before its $b$’s and has equal counts of the two symbols. Conversely, any string $a^n b^n$ can be generated by applying the rule $n$ times. The minimality clause means strings such as $ba$ or $aab$ are not included.

How to test a proposed string

To decide whether a string belongs to a recursively defined set, work backward from the recursive rule or build it forward from a basis string.

For the example above, a nonempty member must begin with $a$ and end with $b$. Remove those two symbols. If the remaining string is empty or can itself be reduced in the same way, the original string is in $S$. For example, removing the outer $a$ and $b$ from $aabb$ leaves $ab$, and removing them again leaves $\varepsilon$. Therefore $aabb\in S$. But $abab\notin S$: after removing the first and last symbols, the remainder is $ba$, which cannot be generated.

Recursive definitions and induction

Recursive definitions naturally support proofs by structural induction. To prove a property holds for every string in the recursively defined set:

• Check the property for each basis string.
• Show that every recursive rule preserves the property.

For $S$, for example, prove that every string has the same number of $a$’s and $b$’s. The basis string $\varepsilon$ has zero of each. If $w$ has equally many of each, then $awb$ adds one of each, so it still has equal counts. By induction, every string in $S$ has equal numbers of the two symbols.

Common mistakes

• Leaving out the alphabet: state the permitted symbols, even if the rules seem to make it obvious.
• Forgetting the minimality clause: otherwise the definition may not specify exactly which strings are included.
• Treating a rule as reversible: “If $w\in S$, then $awb\in S$” allows you to build $awb$ from $w$; it does not automatically say that every string beginning with $a$ and ending with $b$ belongs to $S$.
• Confusing strings with sets: order matters in a string, so $ab$ and $ba$ are different strings.

To define a particular set, write down its base strings and every allowed construction rule. Those details determine the set; the general phrase “recursive definition of a set of strings” does not specify one by itself.