It's a homework problem. Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb.

My idea was: construct a regex that matches everything except bba, construct a regex that matches everything except abb and OR them together.

The first answer I thought of was $a^*b^*|b^*a^*$ and while it does technically guarantee that only one substring will be present at a time (if it is present), it is limiting in that it doesn't accept other perfectly valid strings like $aba$ or $ababa$. How would I go on about constructing such a regex specifically and generally how should I approach constructing regexes to be able to come up with correct regexes?

  • $\begingroup$ If you take the question as written, you can just make regex that recognizes no words at all $\endgroup$
    – Mitch
    Mar 4, 2020 at 17:02
  • $\begingroup$ Either way you would not want to OR the expressions, you would want to AND them $\endgroup$
    – Mitch
    Mar 4, 2020 at 17:17