The Gateway to Computer Science Excellence
+41 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$?

  1. $(0^*10^*1)^*$
  2. $0^*(10^*10^*)^*$
  3. $0^*(10^*1)^*0^*$
  4. $0^*1(10^*1)^*10^*$
in Theory of Computation by Veteran (105k points)
edited by | 4.9k views
which one is correct option?
Any standard method to improve accuracy in these type of questions where we have to compare two RE
Option B)    can not generate 1100 .

So what is the final ans for this question.?????
option b generate 1100 as a substring

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


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

Pritam Dutta & @ joshi_nitish

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

Please Explain ...

6 Answers

+56 votes
Best answer
  1. - 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$)
  2. - is the answer
  3. - between the second and third $1$'s a $0$ is not allowed (eg, $011011$)
  4. - $00$ is not allowed, zero is an even number.
by Veteran (431k points)
edited by
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*)(10*10*) = $\epsilon (1 \epsilon 1 0)(1 0 1 \epsilon)$
@nbnb "11101 is generated as follows:

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?

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

Am I rt?
Srestha..  No it can be generated by B
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 [email protected] 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??




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

+26 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.
by Active (4.7k points)
@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??

+5 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

by Active (1.1k points)
edited by
+1 vote

Here I'm using state elimination method for recognize of RE, after that we can use the property to reach the correct option.

by (471 points)
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.
by Junior (787 points)
–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.
by Boss (19.9k points)
but zero is an even number.
ok, I misinterpreted perhaps.
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?
if i want to generate srting 0000110000 how to generate with B option?
0*(10*10*)*........from first 0* you can generate 0000 then in (10*10*) take fisrt 1 ignore second 0* then take 1 and with last 0* you can generate 0000... so 0000110000 can be produced.
How to produce 10100 using option B??

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,303 answers
105,008 users