The Gateway to Computer Science Excellence
0 votes
78 views
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
0
What does it mean by $r^R$ ?

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

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

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

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?

 

 

 

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

@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 

0
Let's take III.

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

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

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

@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
198,234 comments
104,917 users