# Regular expression with out the substring bab or abb?

I'm having a problem coming up with a regular expression for a language L = {a,b} with out the substring bab or abb? I can come up with the one for just one substring, like

a*(b* aaa* )* b* a* to eliminates the bab and b*(a+ab)* to eliminates the abb substrings.

But putting them together is a huge animal :(

• You can always construct an NFA and convert it into a regular expression. You can first construct an NFA for all words containing bab or abb, then make it into a DFA, then complement it, then convert it into a regular expression. – Yuval Filmus Sep 23 '17 at 22:43
• Think of what string could precede $b$. For example, what could precede $bb$? In this way, try to come up with "building blocks" for strings not containing bab and abb. – Yuval Filmus Sep 23 '17 at 22:46
• "But putting them together is a huge animal" -- How do you "put together" regular expressions? – Raphael Sep 24 '17 at 13:13
• @Raphael we "put together" by concatenation, intersection, and union. – fade2black Sep 24 '17 at 15:51
• @fade2black I am not aware of a canonical regular expression operation that provides intersection. – Raphael Sep 24 '17 at 17:07

There are a couple tricks required to get this right.

First, this particular problem is a lot easier if you approach it backwards, starting at the end of the sting.

(abb,bab) is an exhaustive list of all the cases in which b is preceded by 2 different letters. If you want to exclude these cases, you just have to ensure that b is preceded by less than 2 letters, or a double letter.

Second, notice that these rules imply that if there are 2 bs in a row, then they must be preceded by b all the way to the start of the string. Otherwise the second-to-first b will be preceded by ab.

Working from the end, then, we can have a free mixture of a and aab, and then there are only a few ways to get to the beginning of the string when we encounter a b outside of that pattern:

(ab|b*)(aab|a)*


Thanks for the help, i came up with a solution, although I'm not 100% sure:

0*(1+000*)0*+(1*0*)

Here can use jflap to test a few strings.

• If you're not sure you're correct, try proving that you are. Alternatively, you can construct a DFA for the language along the lines of my comment to the post, take the symmetric different with a DFA generated from you regular expression, and verify that the resulting DFA accepts no string. – Yuval Filmus Sep 24 '17 at 7:12