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

3 Answers 3

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)*
$\endgroup$
5
  • $\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$ Apr 19, 2020 at 13:53
  • $\begingroup$ what is the wrong in this regular? 1*(01+1)*0*1* $\endgroup$
    – khalid J-A
    Mar 21, 2021 at 10:04
  • $\begingroup$ I mean:`1*(01+1)*01* $\endgroup$
    – khalid J-A
    Mar 24, 2021 at 10:18
  • 1
    $\begingroup$ What about 110110? $\endgroup$
    – greybeard
    Apr 10, 2021 at 6:49
  • $\begingroup$ @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. $\endgroup$
    – gnasher729
    Dec 5, 2023 at 15:55
1
$\begingroup$

It should be something like this:

$0?(10?)^*$

Accepts the empty string.

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

Does not accept the empty string.

$\endgroup$
1
$\begingroup$

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^*$
$\endgroup$
2
  • $\begingroup$ (Watch out for markdown to eat characters like asterisks, which it considers special. Consider using $L^AT_EX$.) $\endgroup$
    – greybeard
    Apr 10, 2021 at 6:36
  • $\begingroup$ Does the asterisk in 10* apply to just the 0, or to 10? Can you please give a reference? $\endgroup$
    – greybeard
    Apr 10, 2021 at 6:53

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