The Gateway to Computer Science Excellence

+14 votes

Best answer

Here Total no. of $0$'s to the right of each $1$'s should be even. So, to the left side of every $1$'s no. of $0$'s can be anything.

$L=\{ \epsilon ,0,00,000,01,011,0111,1,11,111,1111,100,10000,100100,10010000...................\}$

Hence,

**$\mathbf{R.E.=0^*(1+00)^*= 0^*(1(00)^*)^* = 0^*(1+(00)^*)^* =0^*(1^*+(00))^* = 0^*(1^*+(00)^*)^*}$**

+3

Actually both Answer is Right.

0*(1+00)* = 0*(1(00)* )* = 0*(1+(00)* )* =0*(1*+(00) )* = 0*(1*+(00)* )*

+4

I didn't use any identity here.It's about logic.

Question is asking regular expression for all strings of 0’s and 1’s in which the total number of 0’s to the right of each 1 is even.

It means before 1 any number of 0's can occur but after one number if 0's should be even

(**including ZERO no. of 0's**).

$0^{*}(1+00)^{*} and \ \ 0^{*}(1(00)^{*})^{*}$ are equivalent.Both generate the same set of strings.

0

As per the question : the total number of 0’s to the right of **each** **1** should be even.

So as per my understanding it should be :

0*(1(00)^+)*.

As for each 1 it should be followed by even 0's.

And if we consider **0*(1+00)* --- > then it will even generate string 11 and here each string is not followed by 0.**

+6 votes

I feel the question is similar to this.

As far as I can think of,

$0^{*}(1(00)^{*})^{*}$

should be able to generate the strings of this language.

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

50,737 questions

57,258 answers

198,087 comments

104,735 users