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?
$\begingroup$
$\endgroup$
3
-
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 RicherbyCommented Oct 19, 2015 at 8:55
-
$\begingroup$ Sure. It's a perfectly reasonable question. $\endgroup$– David RicherbyCommented Oct 19, 2015 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. PinCommented Oct 19, 2015 at 16:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$.
-
$\begingroup$ Its much more abstract view please give me some detail. $\endgroup$ Commented Oct 19, 2015 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$– VorCommented Oct 19, 2015 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$ Commented Oct 19, 2015 at 16:06
-
-
2$\begingroup$ This proof method is called structural induction. $\endgroup$– G. BachCommented Oct 21, 2015 at 11:52