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
