# Regex for bit strings with at least two zeros but no consecutive zeros

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. Can someone help? Thanks!

• Where does the “even number of zeroes” come from? Commented Dec 9, 2022 at 6:30

What does it mean by "no consecutive zeros"? That means there is at least one 1 between any two zeros. You can express it as $$01^*1$$, expecting there might be a 0 downstream.

If there are two non-consecutive zeros, you must have a substring like $$011^*0$$. All other characters must be optional, which should be better expressed separately.

So a possible answer could be $$1^*(01^*1)^*(011^*0)(11^*0)^*1^*$$ It reads as a string that

1. starts with zero or more 1's,
2. followed by zero or more strings each of whom starts with one 0 and ends with 1 with possible more 1's in between,
3. followed by two 0's that are separated by one or more 1's,
4. followed by zero or more strings each of whom starts with one 1 and ends with 0 with possible more 1's in between,
5. followed by zero or more 1's.

Motivated by oerpli's answer, we can actually remove one part of the expression. For example, we can let the two zeros occur at the end, i.e., no zero is after those two zeros. The shortened expression will be $$1^*(01^*1)^*(011^*0)1^*$$

The shortest regex I came up with is: 1*01+0(1+0?)*

1. Start with arbitrary amount of 1s (1*)
2. Exactly one 0 (0)

3. One or more 1s (1+)

4. Another 0: (0)
5. Arbitrarily often ((...)*):
1. One or more 1s (1+)
2. At most one 0 (0?)

You have the "no consecutive zeroes" part correct. However, your answer has two mistakes. As you've noticed, it only matches strings with an even number of zeros; but it also matches the empty string, which it shouldn't.

A string contains at least one zero if it contains a zero, and then maybe some more zeros. If we ignore the ones for a moment, that's $$00^*$$. I think you already know how to modify that so the zeros can't be consecutive.

You start with any number of 1s. Then a zero, one or more 1s, and a zero. That’s the first string in your language. You can follow it by (at least one 1, followed by zero) any number of times, getting more than two zeroes, and then you can add more 1s

$$1^* 011^*0 (11^*0)^* 1^*$$

If you use + as “once or more” then it becomes

$$1^* 0 (1^+ 0)^+ 1^*$$

My solution is 1*(01+){2,}0?

1. (01+){2,} means there are at least two (01+), e.g. 0101, 01101, 011010111
2. Then we should allow any number of 1 at the begining so add 1* at the begining.
3. We should allow 0 at the send, exactly one 0 or no 0. So add 0?

Combine step 1, 2, 3, get the solution 1*(01+){2,}0?

According to oerpli, 1*01+0(1+0?)* is also a good answer.