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

Here, forming the DFA and finding RegExp using elimination method gives RegExp : $(0 + 10^*1)^*$

And, using the RegExp property that : $(a + b)^* = a^*(ba^*)^*$

$(0 + 10^*1)^* = 0^*( 10^*10^*)^*$, $\color{navy}{a= 0, b = 10^*1}$

---

How would you create the 0 (in the middle) for 011011 using option b ?

had it been 0*(0*10*10*)* , then we could have produced 011011.

---

How will option B generate 11101

---

the option B also cannot generate all the strings with  even no. of 1's in it

---

@Arjun Sir,

Option (B) cannot generate 110101

So, which one is the correct here?

---

0*(10*10*)*

0*(10*10*)(10*10*) = $\epsilon (1 \epsilon 1 0)(1 0 1 \epsilon)$

---

@nbnb "11101 is generated as follows:

0*(10*10*)*
0*(10*10*)(10*10*) = $\epsilon (1\epsilon1\epsilon)(101\epsilon)$

---

@ Praveen sir, Since even #1's should be there for any string then $\epsilon$ also belongs to the language where #1's is 0. right?

---

011011

cannot be generated by B) and also cannot generated by C)

Am I rt?

---

Srestha..  No it can be generated by B
0(10*10*)(10*10*)
0(1€10)(1€1€)

---

tnks :)

---

How can you produce "110011" from option B. It is an acceptable language. But I don't think the RE can produce that.

---

011011 production from B:

 

0*(10*10*)*: 0(110)(11)

---

why here 011011 not allowed..?

means why 0 is not allowed in the middle.....?

please clear me ....@Arjun Sir......please....

---

If we consider brackets having * as epsilon (null), then option A,B,C cannot produce the string with consecutive 11. But in that case D would have a 11 as substring. So according to be D is the option.

Correct me if i am thinking wrong.

---

Shamim, you are wrong..

---

@Verma Cant we consider elements inside a bracket (having *) epsilon or null ?

---

Yes you can consider.. And inside and outside epsilons are independent.

Option D is wrong(e.g. it can't generate 0 1's).

---

@srestha 011011 can be produced by option b but not by option c.

---

@nbnb you can check like this

0*(10*10*)(10*10*) it will generate all type of strings 11110,11101,11011,10111,01111

or any type of string you want just put the number at place of *

I hope you will get it.

---

By examining each and every option answer is very clear

(I)$(0^*10^*1)^* \equiv((\epsilon+0+00+00+....).1.(\epsilon+0+00+000+...)1)^*=((1+01+001+0001+..).(1+01+001+001))^*$-In this zeroes cannot occur independently because string of only zeroes has even number of 1's

(C)$0^*(10^*1^*)^*0^* \equiv (0^*(1.(\epsilon+0+00+000+0000+..).(\epsilon+1+11+111+..))^*0^*)$-Here number of 1's can occur freely-So this is also not correct.

(D)Cannot generate $\epsilon$ so throw it.

We are left with B.Answer

---

0$^{*}$(10$^{*}$10$^{*}$)$^{*}$ produce set of all the bit strings with even numbers of 1s.

---

How can we generate 11110 from option B??

---

@Chuzu

$0^*(10^*10^*)(10^*10^*)0^*(10^*10^*)^*$

$\epsilon(1\epsilon1\epsilon)(1\epsilon1\epsilon)0\epsilon=11110$

---

Hello sir! I'm still not able to understand why option C is wrong??

---

@Doodle) answer clearly explains-- in option C strings of the type 011011 (0 between 2nd and 3rd 1) are not generated..

---

String "01011010" cannot be generated by Option B. Please guide.

---

why not?

It can be generated ,  pattern will be like 0(101)(1010)

---

option b is also incorrect then since it doesnt accept 11011

---

can B produce 1100 ?

---

yes it is generating 1100 directly

0*(10*10*)*

ϵ(1ϵ100)

---

@Arjun  sir but even b option isn't generating 0110 string.

---

did you start the timer as soon as you completed the reading the question and stopped it after solving ?

---

How B is the ans? N if Yes then.. How String "1010101" Will be accepted by option B???? Plz someone explain

---

Can option B generate 10111 ????

Can anyone pls explain

---

(a+b)* = a*(ba*)*

0*(10*10*)*

so a = 0, b=10*1 => (0+10*1)*

for 10111 we can take (0+10*1)^2 => 10*110*1 => 10111

---

B can’t generate 1100 so how can B be the answer? 

---

(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.