Regex for bit strings with at least two 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. Can someone help? Thanks!

Answer 1

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 something like $01^*1$, if 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 starts with zero or more 1's, followed by zero or more strings each of whom starts with one 0 and ends with 1 with possible more 1's in between, followed by two 0's that are separated by one or more 1's, followed by zero or more strings each of whom starts with one 1 and ends with 0 with possible more 1's in between, followed by zero or more 1's. Notice the symmetry, which should help your understanding.

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 shorten expression will be, $$1^*(01^*1)^*(011^*0)1^*$$

Answer 2

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

Answer 3

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.