Peter Linz Edition 4 Exercise 3.1 Question 21 (Page No. 77)

Question

Give a general method by which any regular expression $r$ can be changed into $\widehat{r}$ such that $(L(r))^R = L(\widehat{r})$.

Answer 1

The general method is very simple:

A  Regular Expression $r$ can consist of 6 distinct characters.

$(a) x : x \in \Sigma\displaystyle \\ (b) +\displaystyle \\ (c) * \displaystyle \\ (d) Concatenation Operator\displaystyle \\ (e) \lambda\displaystyle \\ (f) \Phi\displaystyle$

Step 1 : Decompose $r$ in $P$ and $Q$ such that, $r=PQ$. Then $r^R = Q^RP^R$

    Repeat this if $P$ or $Q$ can be decomposed.

Step 2 : If any decomposition of $r$, $D$ can be decomposed in $R$ and $S$ such that, $D= R+S$, then keep it intact.

    Repeat Step 1 and Step 2 on $R$ and $S$.

Step 3 : If $D= T^*$, then apply Step 1 and Step 2 on$T$.

Step 4 : If $|D|=1$, so that, $D = \{x: x\in \Sigma\cup\lambda\cup\Phi\}$, then keep it intact.

For example, $(ab)^*(a+b)\underline{(bb)^*}$ The underlined is $Q$ and rest is $P$.

${(bb)^*}^R{((ab)^*\underline{(a+b)})}^R$

${(bb)^R})^*{(a+b)}^R((ab)^*)^R$

${(b^Rb^R})^*{(a+b)}((ab)^R)^*$

${(bb})^*{(a+b)}(b^Ra^R)^*$

$(bb)^*(a+b)(ba)^*$