-1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)*
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 6005 Apr 19 at 13:53
0
$\begingroup$

It should be something like this:

$0?(10?)^*$

Accepts the empty string.

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

Does not accept the empty string.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.