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

$\text{correct Regex would be, RE1=}0^*1[0+10^*1]^* \text{ and RE2=} [0+10^*1]^*10^*$

$\text{please correct me if i am wrong.}$

---

i think 01011 will not belong to your RE.

---

no option can generate 01 , therefore all are wrong!

 

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

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

---

nice

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*