# 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. Apr 19, 2020 at 13:53
• what is the wrong in this regular? 1*(01+1)*0*1* Mar 21, 2021 at 10:04
• I mean:1*(01+1)*01* Mar 24, 2021 at 10:18
• What about 110110? Apr 10, 2021 at 6:49
• @greybeard, that's right. The RE requires all even length strings to start with 1. "01" would be the shortest string that is falsely not recognised. Dec 5, 2023 at 15:55

It should be something like this:

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

Accepts the empty string.

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

Does not accept the empty string.

Any of the following should work:

1. $$(1+01)^*(0+\epsilon)$$
2. $$(0+\epsilon)(1+10)^*$$
3. $$1^*(011^*)^*(0+\epsilon)$$
4. $$(0+\epsilon)(11^*0)^*1^*$$
• (Watch out for markdown to eat characters like asterisks, which it considers special. Consider using $L^AT_EX$.) Apr 10, 2021 at 6:36
• Does the asterisk in 10* apply to just the 0, or to 10`? Can you please give a reference? Apr 10, 2021 at 6:53