Regular expression not containing 101

Question

I came across the regular expression not containing 101 as follows:

0^∗1^∗0^∗+(1+00+000)^∗+(0⁺1⁺0⁺)^∗

I was unable to understand how the author come up with this regex. So I just thought of string which did not contain 101:

01000100

I seems that above string will not be matched by above regex. But I was unsure. So tried translating to equivalent pcre regex on regex101.com, but failed there too (as it can be seen my regex does not even matches string containing single 1.

Whats wrong with my translation? Is above regex indeed correct? If not what will be the correct regex?

Answer 1

Here is a bit shorter expression ^0*(1|00+)*0*$

https://www.regex101.com/r/gG3wP5/1

Explanation:

• (1|00+)* we can mix zeroes and ones as long as zeroes occur in groups
• ^0*...0*$ we can have as many zeroes as we want in prefix/suffix

---

Direct translation of the original regexp would be like

^(0*1*0*|(1|00|000)*|(0+1+0+)*)$

Update
This seems like artificially complicated version of the above regexp:

• (1|00|000)* is the same as (1|00+)*
  • it is almost the solution, but it does not match strings 0, 01.., and ..10
• 0*1*0* doesn't match strings with 101 inside, but matches 0 and some of 01.., and ..10
  • we still need to match those of 01.., and ..10 which have 0 & 1 mixed inside, e.g. 01001.. or ..10010
• (0+1+0+)* matches some of the remaining cases but there are still some valid strings unmatched
  • e.g. 10010 is the shortest string that is not matched by all of the cases.

So, this solution is overly complicated and not complete.