Let L be a language that consists of the set of strings over the alphabet {a, b} generated by the recursive definition I define below:

Recursive definition:

i) Basis: $b \in L $

ii) Recursive Step: if u is in L then $ub \in L, uab \in L, uba \in L$, and $bua \in L$; where u is just some previously (but legal in this particular language) defined string.

iii) Closure: a string v is in L only if it can be obtained from the basis by a finite number of iterations of the Recursive step.

I need to come up with the legal strings of characters from the alphabet {a, b} are allowed in this language which are generated based off the recursive step.

I feel quite stumped when trying to identify these strings. I know my base case will give me a b as my first legal string, but I need to find all possible strings in this language by iterating through the recursive step until I have all acceptable/legal strings.

For instance:

If given some string made up of a's and or b's, how can I trace through the particular language I defined previously and the given string to see if its valid in this language?

Example: is the string bbaaba in this particular language L

I do understand what is being asked and that I must use the recursive step to produce all the legal strings, I just don't know exactly how to go about it in a way that is efficient and accurate. Any help with an explanation is greatly appreciated.


To determine if something is in $L$, you should be able to use your definitions backwards. My algorithm for this works by using a depth first search of the possible strings. Also, when I say undo, I mean that given a string like $ub$, to undo it with $u\in L\implies ub\in L$ would leave us with just $u$.

For the string $bbaaba$, it can only be in $L$ if undoing any of the recursion steps leads to a string that is in $L$. To do this, we first see if we can undo the $u\in L\implies ub\in L$. To do this, we see if we can remove a $b$ from the end. Since we cannot, we move onto the next recursive definition. We try to undo $u\in L\implies uab\in L$. We cannot. We then try to undo $u\in L\implies uba\in L$. We can. This means that $bbaaba\in L \text{ if } bbaa\in L$. We then try to undo $u\in L\implies ub\in L$. That fails. Next $u\in L\implies uab\in L$. That also fails. We then try to undo $u\in L\implies uab\in L$. We cannot. Finally, we try to undo $u\in L\implies bua\in L$. This works and leaves us with $ba$. We go through all the recursive definitions on that string and fail every time. We then have to go back to $bbaaba$, and use the last recursion definition. We then try to undo $u\in L\implies bua\in L$. We can, and we are left with $baab$. We then try to undo $u\in L\implies ub\in L$. We can, and we are left with $baa$. We keep searching until we either end up with $b$ or an invalid string.

  • $\begingroup$ This too is an extremely well explained answer. Just to be sure, each time we successful undo the current string and end up with a new string (of less length), we start at the top/beginning of the recursive step again correct? $\endgroup$ – taylor.tackett Sep 19 '16 at 0:20
  • $\begingroup$ If we exhaust all definitions at one level, we go back up a level. If one of our definitions is satisfied, we go down a level. If you understand a depth first search, the actual details shouldn't be too hard to figure out. $\endgroup$ – AlgorithmsX Sep 19 '16 at 0:25
  • $\begingroup$ Thank you very much, your explanation and comment completely clears up all ambiguities I had. +1 $\endgroup$ – taylor.tackett Sep 19 '16 at 0:51

A small, but important observation is that in the recursive step, either one or two letters are added. Hence, it might be efficient to enumerate these legal strings by increasing length of the string. A start would be:

  1. $b$
  2. $bb$
  3. $bbb$, $bab$, $bba$

Now, to create the strings of length $n$, you only have to consider the strings of length $n-1$ and $n-2$. Of course, this will still become a lot of work, but the amount of legal strings in this language of a certain length can grow very fast, so this is unavoidable.

In order to solve a question such as "Is the string $bbaaba$ in this particular language $L$?" you would have to figure out how such a string could have been created, i.e. which recursive steps were taken to get to this string (sometimes multiple options are possible). It works well to travel through the recursive steps in reverse order: which is the final recursive step one could have taken to reach $bbaaba$? It certainly cannot be $u \rightarrow ub$ or $u \rightarrow uab$. By exploring the other options, you will find that this is not a legal string.

  • $\begingroup$ Beautiful explanation! Great idea about using the length of the string to compute possibilities (when n is a reasonable number of course). And ok that makes sense, so correct me if I'm wrong: let say the conditions in the recursive step were only u → uba and u → bua, would bbaaba then be a legal string? I want to say it would be allowed but still feel ambiguous on it. Also, if you do not violate any of the conditions but do not use all of them, is that string legal? I.e. must the string in question satisfy every restraint given in the recursive step? Or can it leave some out. $\endgroup$ – taylor.tackett Sep 19 '16 at 0:12
  • $\begingroup$ I'm not sure I fully understand your question: in the current rules $bbaaba$ is not a legal string. So certainly, when we remove some options in the recursive step, it still is not a legal string. And we do not have to use all the conditions, for example, $b$ is a legal string, but does not use the recursive step at all. $\endgroup$ – ToucanNapoleon Sep 19 '16 at 10:07

If you generate all words of $L$ of length at most $5$, say, you may notice that each of these words $w$ has the following property:

$|w|_b>|w|_a$, and if $w=uv$ with $u,v\in\{a,b\}^*$, then $|u|_b\ge|u|_a$.

In words, $w$ has more $b$s than $a$s, and no initial segment of $w$ has more $a$s than $b$s.

Clearly the initial word $b$ has this property, and it’s easy to check that if $u$ has the property, so do $ub,uab,uba$, and $bua$. It follows that every $w\in L$ has this property. If we could show that every $w\in\{a,b\}^*$ with this property is in $L$, we’d have a nice characterization of the members of $L$, one that lends itself readily to algorithmic checking.

Suppose that this is not the case, and let $w$ be a shortest counterexample: $w\in\{a,b\}^*\setminus L$, $w$ has the property, and every shorter word in $\{a,b\}^*$ with the property is in $L$.

  • Show that $|w|>2$.
  • Show that $w$ cannot end in $ab$ or $ba$, because if it did, there would be a shorter counterexample.
  • If $w=ubb$ for some $u\in\{a,b\}^+$, then $|ub|_b=|ub|_a$; show that this leads immediately to a contradiction. Thus, $w$ cannot end in $b$.
  • If $w$ ends in $aa$, show that $w=buaa$ for some $u\in\{a,b\}^+$. Show that if $u$ began with $b$, then $ua$ would be a shorter counterexample, while if $u$ began with $a$, then $w=babvaa$ for some $v\in\{a,b\}^+$, and $bvaa$ would be a shorter counterexample. Thus, $w$ cannot end in $a$, either, and there cannot be a counterexample.

This characterization of $L$ makes it easy to determine whether a word over $\{a,b\}$ belongs to $L$ by processing it from left to right as follows.

  1. Start a counter at $0$.
  2. When you read a $b$, add $1$ to the counter.
  3. When you read an $a$, subtract $1$ from the counter.
  4. If the counter ever goes negative, reject the word: it’s not in $L$. Also reject the word if the final value of the counter is $0$.

It would not be hard to convert this algorithm to a deterministic pushdown automaton.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.