in Theory of Computation retagged ago by
16,144 views
16 votes
16 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^*$
in Theory of Computation retagged ago by
by
16.1k views

4 Comments

edited by
I think marks will be given to everyone who attempt this question
0
0
@Arjun sir should the answer be challenged
0
0

D is the correct answer

C can not genrate string 01

B can not genrate string 10

A is genrating Universal language 

0
0
Option d will not generate string 11100011
0
0

3 Answers

32 votes
32 votes
Best answer
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

4 Comments

$010$ string cannot be generated by any of the given options.
2
2
Is the correct regular expression will be (0+10*1)*10*…..??
0
0

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

4 Comments

yes.
0
0

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
0
require simplication of all these regular expression involving Knlee star with concatenation to understand easily. please elaborate further.
0
0
1 vote
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*
by
Answer:

Related questions