Dark Mode

32 votes

Best answer

__Trick for writing reg exp :-__

The Regular expression for the set of all binary strings with **an even number of $1$′$s$:-**

$(0^*10^*10^*)^*+0^*$

$\ $

The Regular expressions for the set of all binary strings with** an odd number of $1$′$s$:-**

1. Remove last $1$, whatever remains is even no. of $1$’$s$, then place $1$ at last

$((0^*10^*10^*)^*+0^*)10^*$

OR

2. Take first $1$ out, whatever remains is even no. of $1$’$s$

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

0

3 votes

Taking each option 1-by-1:

Option A: it is not generate 01 which has odd number of 1.

Option B: it is not generate 10 which has odd number of 1.

option C: it is not generate 01 which has odd number of 1 i.e. force to start with 1 only.

Option D is also not generate 01.

So none of them is correct

Option A: it is not generate 01 which has odd number of 1.

Option B: it is not generate 10 which has odd number of 1.

option C: it is not generate 01 which has odd number of 1 i.e. force to start with 1 only.

Option D is also not generate 01.

So none of them is correct

how Option D is producing the String '01'. What am I Missing ???????

@SomeEarth -

Option D is -> (0*10*10*)*10*

"*" indicates the accompanying string can be absent. It could also be present any number of times. (0*10*10*)* indicates that the entire string 0*10*10* may not be present at all. Even if this string is present, within the string 0*10*10*, "11" will mandatorily be there. The 0s in the string are optional.

Thus option D, (0*10*10*)*10* doesn't accept the string "01". It just accepts the The string it can accept is 0101010, 010101, 10101, 1101, 111 etc.

Hope this helps!

0

1 vote

[(0+1)*1(0+1)*1]*10* cannot generate "01".

(0*10*10*)*0*1 cannot generate "10"

10*(0*10*10*)* cannot generate "01"

(0*10*10*)*10* cannot generate "01".

All given options are wrong. No option generates the set of all binary strings with an odd number of 1's. The following expressions represents the set of all binary strings with odd number of 1's.

I. (0*10*10*)0*10*

II. 0*10*(0*10*10*

(0*10*10*)*0*1 cannot generate "10"

10*(0*10*10*)* cannot generate "01"

(0*10*10*)*10* cannot generate "01".

All given options are wrong. No option generates the set of all binary strings with an odd number of 1's. The following expressions represents the set of all binary strings with odd number of 1's.

I. (0*10*10*)0*10*

II. 0*10*(0*10*10*