retagged by
23,414 views
24 votes
24 votes

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

  1. $((0+1)^*1(0+1)^*1)^*10^*$
  2. $(0^*10^*10^*)^*0^*1$
  3. $10^*(0^*10^*10^*)^*$
  4. $(0^*10^*10^*)^*10^*$
retagged by

3 Answers

Best answer
40 votes
40 votes
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.
selected by
3 votes
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
edited by
1 votes
1 votes
[(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*
Answer:

Related questions

17 votes
17 votes
3 answers
1
31 votes
31 votes
4 answers
3
Arjun asked Feb 12, 2020
7,386 views
Raman is confident of speaking English _______six months as he has been practising regularly_______the last three weeksduring, forfor, sincefor, inwithin, for
8 votes
8 votes
6 answers
4
Arjun asked Feb 12, 2020
5,736 views
His knowledge of the subject was excellent but his classroom performance was_______.extremely poorgooddesirablepraiseworthy