1
$\begingroup$

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

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

2 Answers 2

Reset to default
2
$\begingroup$

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)*
Improve this answer
$\endgroup$
-3
$\begingroup$

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.

JFLAP

Improve this answer
$\endgroup$
1
  • 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$ Commented Sep 24, 2017 at 7:12

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.