3.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^*$
edited | 3.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
+2
Option B)    can not generate 1100 .

So what is the final ans for this question.?????
+3
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

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

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$)
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.
edited by
+33
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

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)$
+1
@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.....?

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.
0
Shamim, you are wrong..
0
@Verma Cant we consider elements inside a bracket (having *) epsilon or null ?
+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).
0
@srestha 011011 can be produced by option b but not by option c.
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.

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

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

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$

edited by
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.
+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??

1
2