snippetMinor
How to prove closure property of regular languages using regular expressions?
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:
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$.
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.