Like the title says, we have the alphabet $\Sigma = \{a,b,c\}$ and the question is asking for the regular expression of the language $L$ that has the property that all strings in $L$ have at least two consecutive $a$'s but no consecutive $b$'s.

By attempt at a solution was this, where $aaa^+$ stands for $aaa(aaa)^*$:

$$(a+c)^*aaa^+(a+c)^*b(a+c)^* + (a+c)^*b(a+c)^*aaa^+(a+c)^*$$

but I know this is wrong since we never get an instance of consecutive $b$'s. Can someone point me in the right direction?


1 Answer 1


You'll need to guarantee the following:

  • at some place, you have $aa$
  • whenever there is a $b$, then there is a different letter between it and any further $b$

So one part of your regular expression will be $aa$, and that'll be need to be "in the middle" since we don't want to exclude the word $bcaab$ for example. The other part needs to take care of the restriction for $b$s.

One way to make ensure the restriction with regard to $b$ is to put at least one letter before every $b$ except for the first $b$ before and the first $b$ after $aa$. So you could do:

$(b + \epsilon)((a+c)^+b)^*(a+c)^*aa(b + \epsilon)((a+c)^+b)^*(a+c)^*$

where $\epsilon$ is the empty word. If you don't want to use $\epsilon$, you can split that expression up into 4 expressions without epsilon and sum them up.

  • $\begingroup$ @g-bach Your expression does not seem to match your example word $bcaab$. Even $bcaa$ is not matched. $\endgroup$
    – J.-E. Pin
    Dec 7, 2013 at 9:29
  • $\begingroup$ @J.-E.Pin Thanks, I had made a mistake; it should be fixed now. $\endgroup$
    – G. Bach
    Dec 7, 2013 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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