How to Determine a Language from a Recursive Definition

The alphabet $\{a,b\}$ tells you which symbols may appear in strings, but it does not say which strings belong to $L$. To determine the language, you need the recursive definition’s base cases and recursive rules. Since those clauses are not included here, the set $L$ cannot be identified uniquely.

The method is to start with the specified strings, repeatedly apply the rules, and include exactly the strings that can be obtained in finitely many applications. The examples below show why the missing clauses matter and how to work with a complete definition.

What a recursive definition must specify

A recursive definition of a language usually gives:

1. Base cases: one or more strings declared to be in the language.
2. Recursive rules: instructions for constructing new strings from strings already in the language.
3. An exclusion convention: usually, that no strings belong except those obtained from the base cases by applying the rules finitely many times.

The third part may be stated as “$L$ is the smallest set satisfying these conditions.” This rules out adding unrelated strings that happen to satisfy a broad description. In many textbook definitions, “smallest” is understood even if it is not repeated explicitly.

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

Consider this complete recursive definition:

• Base case: $\varepsilon\in L$, where $\varepsilon$ is the empty string.
• Rule: if $w\in L$, then $awb\in L$.
• No other strings belong to $L$.

Starting from the base case gives

$$\varepsilon,\quad ab,\quad aabb,\quad aaabbb,\quad \ldots$$

For example, the derivation of $aabb$ is

$$\varepsilon\in L \quad\Longrightarrow\quad a\varepsilon b=ab\in L \quad\Longrightarrow\quad a(ab)b=aabb\in L.$$

The resulting language is $\{a^n b^n:n\geq 0\}$. Every application of the rule adds one $a$ at the beginning and one $b$ at the end, so the strings have the stated form. Conversely, applying the rule $n$ times produces $a^n b^n$ for every nonnegative integer $n$. The “no other strings” clause excludes strings such as $ba$ or $aab$.

Why the alphabet is not enough

Even with the same alphabet, different recursive rules define different languages. For example:

• If the base case is $\varepsilon$ and the rule is “if $w\in L$, then $wa\in L$,” the result is $\{a^n:n\geq 0\}$. The symbol $b$ is allowed by the alphabet but never appears in a generated string.
• If the base case is $\varepsilon$ and the rule is “if $w\in L$, then $awb\in L$,” the result is $\{a^n b^n:n\geq 0\}$.

Thus, knowing only that strings are over $\{a,b\}$ does not tell you whether the language contains $a$, $b$, $ab$, the empty string, or any other particular string.

How to test a string

For a complete definition, test membership by tracing the string back through the recursive rules to a base case. In the second example above, $aabb$ is in $L$ because removing its outer $a$ and $b$ leaves $ab$, and removing those leaves $\varepsilon$. By contrast, $aab$ cannot be reduced to the base case using that rule, so it is not in $L$.

This backward check is useful for small examples, but a convincing membership proof should explain why the reductions follow the rules. To describe the entire language, also show both directions: every generated string has the proposed form, and every string of that form can be generated.

Common mistakes

• Treating the alphabet as the language. The alphabet lists available symbols; a language is a set of strings over those symbols.
• Forgetting the empty string. If $\varepsilon$ is a base case, it belongs to the language even though it contains no letters.
• Applying a rule only once. Recursive rules can usually be applied repeatedly, and sometimes in different orders.
• Adding strings that merely look plausible. A string belongs only if the base cases and rules can generate it.
• Ignoring the smallest-set convention. Without it, conditions that say what must be included may allow additional, unintended strings.

To determine the particular $L$ intended by a problem, the omitted base cases and recursive clauses must be supplied. Once they are available, list short derivations, infer a pattern, and then prove that the pattern describes exactly the generated strings.