Log In
0 votes
Consider the following regular expressions:
I. 0(0+1)*
II. 0* 10*1(0 +1)*
III (0+10)*(1+€)
IV.[(0*10* 10*)* +0*]10*
A language L whose regular expression is r is said to be reverse isomorphic if L(r)= L(r^R). How many of the above regular expressions are reverse isomorphic?
in Theory of Computation
edited by
What does it mean by $r^R$ ?

How can we reverse a regular expression?
They mean to say $[L(r)]^R$.

I think only  II. 0* 10*1(0 +1)* is reverse isomorphic

Well, what we 'think' may not always be correct. If you say that II is reverse isomorphic and the others are not, you must provide a justification as to why II is, and the others aren't.

given regular expressions are along with there meaning

I. 0(0+1)*   all strings starting wiith 0

II. 0* 10*1(0 +1)* all strings containing atleast two 1's

III (0+10)*(1+€)  all strings containing no consecutive 1's

IV.[(0*10* 10*)* +0*]10*  now i don't know exactly what this is representing ,but it does not necessarily start with 1

Reversed expressions can be writtten as below 

1.(0+1)*0    all strings ending  wiith 0

2.(0 +1)*10*10*   all strings containing atleast two 1's

3.(1+€) (0+01)*  all strings containing no consecutive 1's

4.  0*1[(0*10* 10*)* +0*]      

@Lakshay Kakkar  thanks for rectifying ,pls verfify now  that 2nd and 3rd are reverse isomorphic and what about 4th?




You have not reversed the 3rd regular expression correctly. And the exact same mistake has been repeated in 4th aswell.

@Lakshay Kakkar    2nd is reverse isomorphic I have written above

and according to you what should be correct reversed expressions for 3rd and 4th pls tell 

Let's take III.

Correct R.E. : (1+€) (0+01)*

Your R.E.: (1+€) (0+10)*

Can you spot the mistake now?
Yes. It is rev isomorphic as well. Odd number of 1s.

@Lakshay Kakkar thanks bro!!

What was the answer? I feel following:

L1^R = (0+1)*0
L2^R = (0+1)*10*10*
L3^R = (1+e)(0+01)*
L4^R = 0*1[0*+(0*10*10*)*]

L1 can have strings ending with 1, but L1^R cannot, so not reverse isomorphic.

Cant find such things for rest. So I guess answer is 3. What was the solution?

Please log in or register to answer this question.

Related questions

4 votes
3 answers
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
asked May 26, 2019 in Theory of Computation Hirak 793 views
1 vote
0 answers
Let x,y,z be regular expression.Let L1,L2 and L3 be regular expression defined as follows: L1=(x*y)*x*y L2=(x*y)(x*y)* L3=x*y(yx*)*y Find the relation between L1, L2 and L3? I solve such problems by finding strings which one of the language can have and other cannot. But sometimes I get messed up doing so, is there any better approach to solve such questions? Help Please!
asked Jan 7, 2019 in Theory of Computation Shivam Kasat 242 views