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.
Best Answer
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.