The Gateway to Computer Science Excellence
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 by Loyal (5.3k points)
edited by | 78 views
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!!

Please log in or register to answer this question.

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,292 answers
104,917 users