12 votes

Write a 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. Justify your answer.

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

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