HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove closure property of regular languages using regular expressions?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
languagesregularexpressionspropertyproveusinghowclosure

Problem

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?

Solution

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$.

Context

StackExchange Computer Science Q#48436, answer score: 4

Revisions (0)

No revisions yet.