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

B can generate 11011 but C cannot

---

write for exactly 2 1's --> apply a * to get even 1's and now expand it several time (>=2 times) , you will get to see you can merge 0*0* to 0* and that gives you 10*10* as pattern , option 0*(10*10*)* is present.

---

• Leading $0^*$: Matches the initial 0. (String so far: 0)

• Inner loop $(10^*10^*)$ Iteration 1: * Matches 1

  • Matches $0^*$ as $\epsilon$ (empty)

  • Matches 1

  • Matches $0^*$ as $\epsilon$ (empty)

  • (String so far: 011)

• Inner loop $(10^*10^*)$ Iteration 2:

  • Matches 1

  • Matches $0^*$ as $\epsilon$ (empty)

  • Matches 1

  • Matches final $0^*$ as 0

  • (Final string: 011110)

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

@vibhash 0^1 (1 0^0 1 0^1) ^1

---

@R2-D2 how to generate 1100?

 

---

0^0 (1 0^0 1 0^2) ^1 = ϵ(1ϵ100) = 1100 @Joyjit_das

 

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.

Answer 5

B.Correct answer

Using state elimination method

Answer 6

The best way to find correct answer is option elimination method. We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
hence B is the answer

Comments

ntg