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 :(

  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 23 '17 at 22:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 23 '17 at 22:46
  • $\begingroup$ "But putting them together is a huge animal" -- How do you "put together" regular expressions? $\endgroup$ – Raphael Sep 24 '17 at 13:13
  • $\begingroup$ @Raphael we "put together" by concatenation, intersection, and union. $\endgroup$ – fade2black Sep 24 '17 at 15:51
  • $\begingroup$ @fade2black I am not aware of a canonical regular expression operation that provides intersection. $\endgroup$ – 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:


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


Here can use jflap to test a few strings.


  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 24 '17 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.