Regex for bit string containing at least 2 zeros but no consecutive zeros.

Question

This is what I have:

(1*011*011*)*

But I don't think this is accounting for an odd number of zeros, like "10101010101111". I think I have the right expression that satisfies no 2 consecutive zeros and even number of zeros.

Answer 1

I'll get you started.

You need to have two zeroes, so start by putting those in your regex, leaving space between, before and after:

$$ \_\_\_\_\_\_0\_\_\_\_\_\_0\_\_\_\_\_\_ $$ Now, consider the space on the left. Every zero in this region is followed by a $1$. Therefore, this portion can be broken into sums of $(01)$ and $1$, so it is $(01|1)^*$: $$ (01|1)^*0\_\_\_\_\_\_0\_\_\_\_\_\_ $$ What about the space in the middle? It has similar rules, but we cannot quite use the same regex $(01|1)^*$ we used on the left. The problem is that this can begin with a zero, which would cause a $00$ with the first $0$ we placed. How can you fix this?