GATE CSE 2010 | Question: 39

Question

Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$?

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

Comments

option a . is incorrect because  the string end with 0 cannot be generated i.e 110

option b. is incorrect because string “110101” is not constructed which has even number of 1’s and also it can generate epsilon .

option c . is incorrect because string “110101” is not constructed .

option d .is incorrect because string “110101” is not constructed .

→ there is no correct answer

---

@abhishek_(123)

Option B can construct 110101 → 

First two 1 and one 0 using (10*10*) => 110

Next 101 using (10*10*) => 101

---

option C not able to genrate string 101011011

Answer 1

• A. - If the string contains a $1$, it must end in a $1$ hence cannot generate all bit strings with even number of $1$'s (eg, $1010$)
• B. - is the answer
• C. - between the second and third $1$'s a $0$ is not allowed (eg, $011011$)
• D. - $00$ is not allowed, zero is an even number.

Comments

(0+10*1)^4 = 11(0+10*1)^2= 1100

---

why can’t C generate 011011, it can easily do that? Help

---

once you use 0*(10*1) ,after that if we need 0 only option is to use the middle one,so if we use the (10*1),again then, it can’t generate only single 0,it generates 1 __as many 0’s_,then 1.

Answer 2

(A) ( 0 * 10 * 1) * --->0110(valid string) not possible to produce from this Regular Expression.

(B) 0 * (10 * 10 *) * ---> Produces all strings with even number of 1's.

(C) 0 * (10 * 1 ) * 0 * ----> 11011(valid string) cannot be produced from this.

(D) 0 * 1 (10 * 1) * 10 ---> epsilon or 0 (valid strings) can not be produced.( even number of 1's includes zero number of 1's)

Therefore Answer : B Correct.

Comments

@prasanna u take R.E of option c is wrong . bcz instead of 0*(10*1*)*0*  this .  it is given as 0*(10*1)*0* just check it out

---

 Prasanna  how from option C u generate 1 as substring??

---

Edited

---

Devwritt

U have edited the option but the explanation for C is wrong. as here the option C can generate 11011...but in the actual paper the option C was different.

Answer 3

 method 1: draw the DFA and then derive reg ex from it 

   

method 2: by verification 

option a. does n't generates strings ending with 0 ex:1100

option c :does n't generates strings like 110011,1101111,011011,...i.e it does n't producing 0 between 2nd 1 and 3rd 1 in the string

option d: does n't generate $\epsilon$ 

option b: is the answer

Answer 4

We can omit out A because it cannot generate strings ending with 0 like 00

Omit D bcoz it cannot generate epsilon

now for B and C .we can clearly observe that C is a subset of B .Any language generated by C can be generated by B so B is the correct option.