How would I start the recursive definition of the following language:

L over {a, b} such that L consists of strings in which each occurrence of b is immediately preceded and followed by an a

The 'and' part is causing me problems with this problem and I don't see a clean way to gurantee the occurence being preceeded and followed recursively.

The recursive definition structure is as follows:

Basis: The base we have to start with for the recursion Recursive step: How we generat ethe language from the basis Closure: Trivial to state

My thought process on this:

We can have lambda, because no b's or no a's doesn't apply to the condition.

My attempt so far:

Basis: $ \lambda \in L $

Recursive Step: If $ w\in L $ then $ aw, wa, babw, waba \in L $.

What i don't see is how th break the recursive step to account for being able to place b's anywhere in $ w\in L$ such that the condition is satisfied.


There is no problem to obtain $b$'s anywhere in the string: basically you can just "read" the string from left to right, and add the $aba$ to the end. That leaves one with only two recursive steps: if $w\in L$, then $wa\in L$ and $waba\in L$.

A bigger problem is that you now do not generate strings like $ababababa$!

This can be handled by having rules like: if the string ends with a $a$ we can add $ba$ to the end.

| cite | improve this answer | |
  • $\begingroup$ That makes sense. SO I take it the other answer incorrect? $\endgroup$ – Overflow2341313 Dec 14 '17 at 1:44
  • $\begingroup$ If $ababa$ is not generated, the rules are incomplete. $\endgroup$ – Hendrik Jan Dec 14 '17 at 1:47
  • $\begingroup$ Looking over this again and I came up with regular expression $ (a^+b)^+a^+ \cup a^* $ to describe the language, but I still fail to see how to properly describe the recursive step witht he additional rules you mention. I know a regex can be converted to a recursive definition Just don't see where to go with this. So, far my recursive step is: If $ w \in L $ then $wa, aw, waba \in L $. If w ends with an a then $ wba \in L $ and if w starts with an a then $ abw \in L $. $\endgroup$ – Overflow2341313 Dec 14 '17 at 17:19
  • $\begingroup$ You only need to extend the strings in one direction (say to the right). A possible formulation for the special case might be: if $wa\in L$ then $waba\in L$. $\endgroup$ – Hendrik Jan Dec 14 '17 at 19:36
  • $\begingroup$ Ah, that's much cleaner. Thank you. Finally understood what you meant by only needing one direction missed the part about being able to read left to right and hence forming all strings in that way recursively. $\endgroup$ – Overflow2341313 Dec 14 '17 at 19:38

It can be:

Basis: $ \lambda \in L $

Recursive Step: If $ w\in L $ then $ aw, wa, abaw, waba \in L $.

You can generate with the above rules all strings in the language.

| cite | improve this answer | |
  • $\begingroup$ How is baw following? It's not preceeded by an $ a $. From the basis we can start with lambda so that's saying $ baw $ can be in the language which breaks the condition of the language. I just realized my attempt is also wrong because of this. $\endgroup$ – Overflow2341313 Dec 14 '17 at 0:58
  • $\begingroup$ @Overflow2341313 I can't get the problem. why $baw$ can breaks the rule?! place $w = \lambda$, hence, $ba$ is in $L$ and it is true. $\endgroup$ – OmG Dec 14 '17 at 1:04
  • $\begingroup$ perhaps I misunderstand the wording of the problem. As I understand it it saying a string is only in the language if an a occurs before and after every b. So ba wouldn't be in L but aba would. $\endgroup$ – Overflow2341313 Dec 14 '17 at 1:05
  • $\begingroup$ @Overflow2341313 OK. I did't see proceeded! Now, the answer is updated. $\endgroup$ – OmG Dec 14 '17 at 1:10

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.