0
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I generally find it easier to construct regular expressions first and then the DFA. $\endgroup$
    – Jake
    Commented Jul 6, 2015 at 2:49
  • $\begingroup$ possible duplicate of How to prove a language is regular? $\endgroup$
    – D.W. ♦
    Commented Jul 6, 2015 at 2:50
  • $\begingroup$ @D.W. How is this duplicate? The answer you referenced appear to be very high level (generic). like how to program in java as opposed to how to write a linked list in Java. My question is how to write a specific regular expression for assuming a Regular Language. $\endgroup$
    – GuyEpsilon
    Commented Jul 6, 2015 at 3:07
  • $\begingroup$ We expect you to make a significant effort before asking here, including searching on this site and consulting the resources we already have here, and to show us in the question what you've tried. Your question is very basic. I recommend that you study the material found in that question, then work through the techniques there and apply it to your problem. I think you'll find that the techniques there will enable you to solve your own problem. If you're still stuck, edit the question to show how you worked through those techniques and where specifically you got stuck when applying them. $\endgroup$
    – D.W. ♦
    Commented Jul 6, 2015 at 3:09
  • $\begingroup$ @D.W. I've added additional info to show how I've worked through the technique of using Regular Expression. Thanks! $\endgroup$
    – GuyEpsilon
    Commented Jul 6, 2015 at 3:29

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$

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.