# A regular expression for all strings over $\{a,b\}$ which do not have both substrings $bba$ and $abb$

I am looking at the answer in a solution manual to the following question.

Let the alphabet $= \{a,b\}$. Write regular expressions for:

• all the words that don't have both substrings $bba$ and $abb$.

$a^*(baa^*)^*b+b^*(a^*ab)^*a^*$

I don't think this is correct, since it can't make $abb$, which is in the language. So it's got to be wrong.

So I came up with my own. Would this be all the words that don't have both substring $bba$ and $abb$?

• $(a+ba)^*(bb+b+\lambda)$

Or maybe this one should work

• $(b+\lambda)(ab+a)^*+b^*$

(In the above $\lambda$ is the empty string.)

• I think the solution manual is interpreting the question to mean, strings that have neither bba nor abb (so abb is not in the language), whereas you are interpreting it to mean, strings that may have one or the other of bba and abb but don't have both of them. Feb 17, 2014 at 9:23

The regex a*(baa*)*b+b*(a*ab)*a* does match abb:

• a* matches a
• (baa*)* matches empty string
• b+ matches bb,
• (a*ab)*a* matches empty string.

Also, both of your regexes match bbabb which shouldn't be matched according to the task. And what is the point of bb+b+, isn't it the same as bbb+?

Not sure what are you trying to accomplish with "^ is an empty string by the way", but usually ^ matches the beginning of the string

• We are talking about basic regular expression syntax. Plus stands for union and there are no extensions like the caret anchoring the match to the beginning of the word. Feb 23, 2017 at 8:01
• @FabioSomenzi sometime in these two years it was edited to replace ^ with $\lambda$, hence my comment on the earlier version Feb 27, 2017 at 2:01
• I had not noticed it had been two years, but I had checked the edit history and I was aware of what had caused the confusion. Feb 27, 2017 at 2:05

These are incorrect regular expressions. We generate $bba$ from the second part.

I think $b^*+a^*(ab)a+a^*(ba)a+a^*ba(a+ab)a+a^*ab(a+ab)a$ may be a correct regular expression.

The correct regular expression is $$b^*+a^*(a^*aba^*)^*+a^*(a^*ba)^*a^*(V+b)+a^*(ba)^*(a+ab)^*a+a^*(ab)^*(a+ab)*.$$

• $ababaab$ accepted
• $abababaab$ accepted
• $baababaab$ accepted
• $ababba$ Rejected