0
$\begingroup$

The answer is

$1^*01^*01^*+1^*(0+00+\in)1^*$

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).

$\endgroup$
1
  • 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
    Nov 10 '21 at 9:33
1
$\begingroup$

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))^*$$

$\endgroup$
3
  • $\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
    Nov 10 '21 at 11:10
  • $\begingroup$ @custep It is not since your expression does not accept the string $00$. $\endgroup$
    – Nathaniel
    Nov 10 '21 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
    Nov 10 '21 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.