0

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

user642796
  • 52,188
manual
  • 61
  • 8
  • 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. – Gerry Myerson Feb 17 '14 at 09:23

2 Answers2

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

mniip
  • 450
  • 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. – Fabio Somenzi Feb 23 '17 at 08:01
  • @FabioSomenzi sometime in these two years it was edited to replace ^ with $\lambda$, hence my comment on the earlier version – mniip Feb 27 '17 at 02: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. – Fabio Somenzi Feb 27 '17 at 02:05
-2

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
user642796
  • 52,188
tanweer
  • 1