The answer is


If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice?

How do I understand what the regular expression is doing just like in this case here.

I think I can create DFA for this, but not sure if that would help me to create regular expression(I know there are posts to convert dfa to regular expression but I don't want that hassle).

  • 1
    $\begingroup$ $101010101010$ isn't accepted by this regex, for example. But it would be in the language since it doesn't contain $3$ consecutive $0$s. $\endgroup$
    – nir shahar
    Commented Nov 10, 2021 at 9:33

1 Answer 1


If you don't want to go through a DFA (which would definitely be the easiest systematic way of doing this), you can approach it by viewing the language as strings of 2, 1 or 0 zeros interleaved by ones:

$$(00 +0 + \epsilon)(1(00 + 0 + \epsilon))^*$$

  • $\begingroup$ stackoverflow.com/questions/26365602/… I use this dfa and I got regular expression $(1+01+001)^* + (1+01+001)^*0+(1+01+001)^*0$. I used arden's theorem. Is this also correct? $\endgroup$
    – custep
    Commented Nov 10, 2021 at 11:10
  • $\begingroup$ @custep It is not since your expression does not accept the string $00$. $\endgroup$
    – Nathaniel
    Commented Nov 10, 2021 at 11:51
  • $\begingroup$ I got it correct. It was typing mistake the last one $(1+01+001)^*00$ Thanks a lot for correction. $\endgroup$
    – custep
    Commented Nov 10, 2021 at 12:24

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.