search
Log In
0 votes
248 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
edited by
248 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!!

0
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
1
793 views
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
3
242 views
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
...