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

Question

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

The answer given was

$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.)

Answer 1

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