The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+37 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 (99.6k points)
edited by | 4.2k 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 ...

5 Answers

+50 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 (418k points)
edited by

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.

+20 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.6k 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??

+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

by Junior (939 points)
edited by
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 (401 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
49,984 questions
55,138 answers
85,163 users