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

3,556

Solution 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.

Solution 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:

$b$
$bb$
$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.

3,556

taylor.tackett

Northern Arizona University '17 Computer Science (BS) Mathematics (Minor)

Updated on August 01, 2022

Comments

taylor.tackett 10 months

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.
taylor.tackett over 6 years

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.
taylor.tackett over 6 years

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?
AlgorithmsX over 6 years

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.
taylor.tackett over 6 years

Thank you very much, your explanation and comment completely clears up all ambiguities I had. +1
HarrySmit over 6 years

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.