[Solved]: Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s

Problem Detail: 

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?

Asked By : noobProgrammer

Answered By : G. Bach

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18701

3.2K people like this

 Download Related Notes/Documents