[Solved]: Regular expression of a language over {a,b,c} which does not contain substring bbb

Problem Detail: 

I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the Regular Expression but still stuck as I found the DFA a bit complicated. I appreciate any help. Thanks!!!

Ok, here is the Regular Expression I've worked on to help me solve the above question. ac[(acb)* U (acbb)]ac*

Test: aaaa ccccc acbacbacb aaaaaaa ccccc (OK) aa acbb acbb acbb acbb cccccccc (OK)

But how about cab or cabb? I then modified the above expression to: ac[(acb)* U (acbb)* U (cab)* U (cabb)]ac*

I'm I heading to the right direction?

Thanks again!

Asked By : GuyEpsilon

Answered By : Jake

The following regular expression (where $\cdot$ stands for $a|b|c$) will match all strings with lengths divisible by 3 not containing the string $bbb$ and not starting with a b.

$((a|c)\cdot\cdot)^*$

Can you modify this to get the expression you want?

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents