Question

Consider the following regular expressions:

I. 0(0 + 1)*
II. 0*10*1(0+1)*
III. (0+10)*(1+$\in$)
IV. [(0*10*10*)+0*]10*
How many of the above regular expressions are reverse isomorphic L(r)=L(r^{R}) ?

• A. 0
• B. 2
• C. None of these
• D. 1

Answer 1

The correct option is C None of these

II. III and IV are reverse isomorpluc.
I denotes strings starting with 0. However its reversal will have string ending with 0. Therefore 1 is not reverse isomorphic.
II is reverse isomorphic as it denotes string containing at least two 1's and same goes for its reversal as well.
The regular expression for III is (0 + 10)* (1 + $\in$) and its reversal will be (1 + $\in$) (0 + 01). Clearly both regular expressions generate the same languge that is the set of strings which don't have any consecutive 1;s. So III is also reverse isomorphir.
IV is the regular expression for odd number of ones and its reversal also represent the same languge and so IV is also reverse isomorphic.