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

regular expressions

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

Best Answer

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

Related Question