edited by
1,537 views
12 votes
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.
edited by

3 Answers

Best answer
14 votes
14 votes

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

0 votes
0 votes

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

Related questions

9 votes
9 votes
1 answer
1
go_editor asked Jun 1, 2016
833 views
Give a context-free grammar $G$ that generates $L = \{0^i1^j0^k \mid i + k = j\}$.Prove that $L = L(G)$.
1 votes
1 votes
0 answers
2
go_editor asked Jun 1, 2016
513 views
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...
2 votes
2 votes
2 answers
4
go_editor asked Jun 1, 2016
1,050 views
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 ...