The Gateway to Computer Science Excellence

+39 votes

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$?

- $(0^*10^*1)^*$
- $0^*(10^*10^*)^*$
- $0^*(10^*1)^*0^*$
- $0^*1(10^*1)^*10^*$

0

+2

Option C is different in actual paper . Otherwise according to the options given here both B and C will give correct answer i guess.

0

@Pritam,

if you take original option C) also, then it is also not correct,

because it can generate 111, 11111... i.e odd numbers of 1's

if you take original option C) also, then it is also not correct,

because it can generate 111, 11111... i.e odd numbers of 1's

0

I know using original option C we can have 111,11111 thats why only B is correct. I meant to say, here (in gateoverflow) the given option C is same as B

0

@ Pritam Dutta & @ joshi_nitish

How you people are generating Odd no. of 1's by the Option C.

Please Explain ...

+52 votes

Best answer

+37

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}$

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

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

+1

How would you create the **0 (in the middle)** for 011**0**11 using **option b** ?

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

+1

@nbnb "11101 is generated as follows:

0*(10*10*)*

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

0*(10*10*)*

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

0

@ 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?

0

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

0

why here 011011 not allowed..?

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

please clear me [email protected] Sir......please....

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

please clear me [email protected] Sir......please....

0

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.

Correct me if i am thinking wrong.

+1

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

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

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

0

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

0

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

(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

+22 votes

(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 * ----> 1(not valid string) can 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.

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

(C) 0 * (10 * 1 *) * 0 * ----> 1(not valid string) can 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.

+4 votes

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

0 votes

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.

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.

0 votes

–3 votes

This will be D. Because as given in the question that L is the set of all the bit strings with even number of 1's, which states that there should be atleast two 1's, this condition is only enforced by option D. In rest all you can have null as a string which is not the desired case.

0

Only the number of 1s should be even and since nothing is given about the number of 0s, string can contain any number of 0s without any restriction right? So, It shouldn't matter if the regex produces 00 right? Option D also accepts even number of 1s right?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,185 answers

193,939 comments

94,696 users