The Gateway to Computer Science Excellence
+11 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.
in Theory of Computation by Veteran (105k points)
edited by | 530 views


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...................\}$


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

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

Actually both Answer is Right.

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


@LeenSharma How you write this bro? Which identity?

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


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.

Even I got  0*(1(00)*)* :)

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 :


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.



what about following?

(1(00)*)* + 0*

   Zero is also an even number right?


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



can we have like

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


 Check for string 0100.

+6 votes

I feel the question is similar to this.

As far as I can think of,


should be able to generate the strings of this language. 

by Active (1.8k points)
0 votes

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

by (487 points)
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.
I was formally applying the algorithm to reduce, not a big deal.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,258 answers
104,735 users