search
Log In
12 votes
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.
in Theory of Computation
edited by
755 views
3
0*(1(00)*)*?????
0

0*(1(00)*)*

I got the same and seems correct. 

3 Answers

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


edited by
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

Actually both Answer is Right.

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
what about following?

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

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

9 votes
1 answer
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)$.
asked Jun 1, 2016 in Theory of Computation jothee 480 views
1 vote
0 answers
2
193 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 vertex $s$ and a designated destination vertex $t$. Let $P(v)$ denote the ... .]
asked Jun 1, 2016 in Algorithms jothee 193 views
1 vote
0 answers
3
196 views
A school database maintains the following relations for its students, teachers and subjects: Student(st_name, st_address, class, section, roll_no, regn_no) Teacher(t_name, t_address, tel_no) Subject(s_name, t_name, text_book, class) Consider the following constraints on the existing ... in Class V and reside in Baranagar (name of a locality). Consider that any address offers a locality name.
asked Jun 1, 2016 in Databases jothee 196 views
2 votes
2 answers
4
446 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 expression for the probability that the error will be detected.
asked Jun 1, 2016 in Computer Networks jothee 446 views
...