3
$\begingroup$

I know that we can prove closure of two regular languages under operations like union, intersection, concatenation etc. by constructing NFAs for them but how to do the same thing using regular expressions, specifically proving that reversal of a regular language is closed using regular expression?

$\endgroup$
  • 2
    $\begingroup$ By far the easiest way to show that regular expressions are closed under reversal is to convert to an NFA, reverse that and convert back, which is exactly what you don't want to do. Although it's surely possible to prove that regular expressions are closed under reversal without going via automata, I suspect it would be sufficiently horrible and unenlightening that there'd be no reason to ever do it. $\endgroup$ – David Richerby Oct 19 '15 at 8:55
  • $\begingroup$ Sure. It's a perfectly reasonable question. $\endgroup$ – David Richerby Oct 19 '15 at 9:20
  • 2
    $\begingroup$ @david-richerby I strongly disagree with your first comment. If you convert your "easiest way" to an algorithm, its complexity will be much worse than with the algorithm given by Vor. $\endgroup$ – J.-E. Pin Oct 19 '15 at 16:20
4
$\begingroup$

You can prove it using this approach:

if $E$ is a regular expression then you can recursively define its reverse in this way:

  • if $E = \emptyset$ then $E^R = \emptyset$
  • if $E= (E_1)$ then $E^R = (E^R_1)$
  • if $E = a \in \Sigma$ then $E^R = a$
  • if $E = E_1 \cdot E_2$ then $E^R = E^R_2 \cdot E^R_1$
  • if $E = E_1 \cup E_2$ then $E^R = E^R_1 \cup E^R_2$
  • if $E = E_1^*$ then $E^R = E^{R\,*}_1$

You can prove that each "step" is correct and after a finite amount of transformations the procedure ends. At the end you get a regular expression (recursively built from $E$) that defines $E^R$.

$\endgroup$
  • $\begingroup$ Its much more abstract view please give me some detail. $\endgroup$ – OldSchool Oct 19 '15 at 11:13
  • $\begingroup$ @Rouftantical: very informally: you can define the reverse of a regular expression $E$ (that represents a regular language $L_E$) using another regular expression $E^R$ which is built recursively (that represents a regular language $L_{E_R}$); for all strings $w$, $w \in L_E$ if and only if $w^R \in L_{E^R}$. $\endgroup$ – Vor Oct 19 '15 at 12:11
  • 2
    $\begingroup$ Since $\cup$ is also commutative you have now shown that the reverse of a language given by a regular expression is represented by the mirror image of the original expression! (Well, assuming you view the expression as a tree with operators in the nodes.) $\endgroup$ – Hendrik Jan Oct 19 '15 at 16:06
  • $\begingroup$ @HendrikJan: Yes, you're right! $\endgroup$ – Vor Oct 19 '15 at 16:58
  • 1
    $\begingroup$ This proof method is called structural induction. $\endgroup$ – G. Bach Oct 21 '15 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.