# ISI2013-PCB-CS-4b

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

edited
3
0*(1(00)*)*?????
0

0*(1(00)*)*

I got the same and seems correct.

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)^*)^*}$

edited
0
is there any string that 0*(1(00)*)* could not generate. Otherwise both could be answer
1
I think here both can do the required job.
3

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

0

@LeenSharma How you write this bro? Which identity?

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
Thanks!
0
Even I got  0*(1(00)*)* :)
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.

0

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

Zero is also an even number right?

0

This R.E. can't able to generate strings like 01,011,0111.........

0

@LeenSharma

can we have like

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

0

Check for string 0100.

0
How can we write $0^*(1+00)^*$. This Regular Expression will also generate 1,11,111... which should not be accepted. I think only $0^*(1(00)^*)^*$ and it's various other forms will work.

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.

I tried making an FSM and then reducing it to get 0*1(1 + 00)*, which accepts all legal strings.

0
your FSM in the first step is already minimized and is generating o*1(1+00)*. Why are you unnecessarily adding epsilon moves and removing trap state, which is indeed giving you more states that first fsm. You can simply reduce it to 3 states by just ignoring trap state in nfa.
0
I was formally applying the algorithm to reduce, not a big deal.

## Related questions

1
480 views
Give a context-free grammar $G$ that generates $L = \{0^i1^j0^k \mid i + k = j\}$. Prove that $L = L(G)$.
1 vote
A connected, simple, undirected planar graph $G(V, E)$ is given where $V$ denotes the set of vertices and E denotes the set of edges. In $V$, there is a designated source vertex $s$ and a designated destination vertex $t$. Let $P(v)$ denote the ... .]
A block of bits with $n$ rows and $m$ columns uses horizontal and vertical parity bits for error detection. If exactly 4 bits are in error during transmission, derive an expression for the probability that the error will be detected.