Let L be the set of strings over {a, b} generated by the recursive definition:

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.