GATE CSE 2020 | Question: 7

Question

Which one of the following regular expressions represents the set of all binary strings with an odd number of $1’$s?

• A. $((0+1)^*1(0+1)^*1)^*10^*$
• B. $(0^*10^*10^*)^*0^*1$
• C. $10^*(0^*10^*10^*)^*$
• D. $(0^*10^*10^*)^*10^*$

Comments

D is the correct answer

C can not genrate string 01

B can not genrate string 10

A is genrating Universal language 

---

Option d will not generate string 11100011

---

here we can apply   method like reg exp that contain even no of 1’s

 

0*(10*10*)*

 

reg exp that contain odd no of 1’s

0*(10*10*)*10*

Answer 1

Regular expression in option A cannot generate $001$
Regular expression in option B cannot generate $100$
Regular expression in option C cannot generate $001$
Regular expression in option D cannot generate $001$

Hence, mark was given to everyone in GATE for this question.

Comments

$010$ string cannot be generated by any of the given options.

---

Is the correct regular expression will be (0+10*1)*10*…..??

---

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^*)$

Answer 2

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

Comments

yes.

---

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!

---

require simplication of all these regular expression involving Knlee star with concatenation to understand easily. please elaborate further.

Answer 3

[(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*