The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
3k views

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^*$
asked in Theory of Computation by Veteran (103k points)
edited by | 3k views
0
which one is correct option?
0
Any standard method to improve accuracy in these type of questions where we have to compare two RE
+1
Option B)    can not generate 1100 .

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

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

4 Answers

+43 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.
answered by Veteran (359k points)
edited by
+31
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}$
+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.

0
Arjun sir please derive 010100 from the RegEx given in option B.
0

How will option B generate 11101

0
the option B also cannot generate all the strings with  even no. of 1's in it
0
@Arjun Sir,

Option (B) cannot generate 110101

So, which one is the correct here?
+6
0*(10*10*)*

0*(10*10*)(10*10*) = $\epsilon (1 \epsilon 1 0)(1 0 1 \epsilon)$
0
@nbnb "11101 is generated as follows:

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?
+1
011011

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

Am I rt?
+2
Srestha..  No it can be generated by B
0(10*10*)(10*10*)
0(1€10)(1€1€)
+1
tnks :)
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

011011 production from B:

 

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

0
why here 011011 not allowed..?

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

please clear me [email protected] Sir......please....
+13 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.
answered by Active (4.8k points)
+2
@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
0

 Prasanna  how from option C u generate 1 as substring??

0
1 cannot be produced from option C. Please correct it.
0 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

answered by Junior (727 points)
edited by
–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.
answered by Boss (19.7k points)
+2
but zero is an even number.
0
ok, I misinterpreted perhaps.
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?
0
if i want to generate srting 0000110000 how to generate with B option?
0
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.
0
How to produce 10100 using option B??


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

41,064 questions
47,662 answers
147,317 comments
62,381 users