Write a regular expression for binary strings with at least two 0s but not consecutive 0s.

Try the new Google Books

Check out the new look and enjoy easier access to your favorite features

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?

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

The regexp you post is erroneous, it suffices to note that it has a 0+ subsequence, which should admit a sequence of one or more 0s. It can be corrected with this solution:

or with + operator

An explanation of it should be: First skip al the ones that start your expression with the 1* subpattern, so you get to the first 0, then skip at least one 1, and all the 1s following it (with subpattern 1+) up to the second 0, so we have just matched the minimum length string that matches you regular language. Once here, all the rest is optional, we need to repeat any number of times the pattern 1 with an optional trailing 0 (as in 10?), or there should be two consecutive 0s. You can check it in this demo, that contains all the possible strings from 1 to 8 characters, and the matching or not of them.