GATE CSE 1987 | Question: 2h

Question

State whether the following statements are TRUE or FALSE:

Regularity is preserved under the operation of string reversal.

Comments

Regular language is closed under

• Union
• Intersection
• Kleene Closure
• Concatenation
• Complementation
• Difference
• Reversal

---

Not closed under subset operation.

---

Also, Not Closed Under Superset operation.

Answer 1

Operation of String Reversal:

e.g. L = { b,ab,aab,aaab,..} Reversal of L: $L^{R}$ = {b,ba,baa,baaa..} 

1. Proof by Reg Ex.

R1 = a*b & $R1^{R}$ = ba*. Therefore $L^{R}$ is also regular.

All Reg Ex can be reversed which results in Reg Ex. 

e.g. :     L                      $L^{R}$

       r + s                        $r^{R}$ + $s^{R}$

        rs                           $s^{R}$$r^{R}$

        r*                            ($r^{R}$)*

2. Proof by DFA

                https://gateoverflow.in/80589/gate-cse-1987-question-2h?show=80593#a80593

 

Therefore, Regular Languages are closed under Reversal of Strings.