# Regular expression without 00 as a substring

I want to create a regular expression for the language:

$$L=\{w \in \{0,1\}\mid w \text{ does not contain 00 as a substring}\}.$$

I've tried various things, but I can't seem to get the correct regular expression.

First, let's start by enumerating the building blocks of length 2.

S = { 01, 10, 11, 00 }


We can immediately remove 00

S = { 01, 10, 11 }


Next, notice 10 + 01 will create a sequence of 00. So, let's remove 01 (10 could also be removed.

S = { 10, 11 }


Our basic solution is (10 + 11)*

However, this does not account for Empty Set + 0 + 1. It also does not account for odd length strings.

Final Solution

(E + 0 + 1)(10 + 11)*

• The (10 + 11)* assumes that 0s occur only in the second position out of every 2 characters. They could occur in the first position as well. – 6005 Apr 19 at 13:53

It should be something like this:

$$0?(10?)^*$$

Accepts the empty string.

$$0(10?)^*|(1^+0?)^+$$

Does not accept the empty string.