Prove by structural induction that if R is a regular express

Prove by (structural) induction that, if R is a regular expression describing the language L, then there must exist a regular expression R to the power of r describing the langue L to the power of r consisting of the reverse of all strings in L.

Solution

Base case:

R =

L(R) = , so R^r =

R = a

L(R) = a, we can see that R^r = a

Induction steps:

Union: R1 U R2

reverse(L(R1 U R2)) = reverse(L(R1) U L(R2)) = reverse(L(R1)) U reverse(L(R2)) = L(R1^r) U L(R2^r) = L(R1^r U R2^r)

Concatenation: R1.R2

reverse(L(R1 U R2)) = reverse(L(R1).L(R2))

So any string belonging to L(R1.R2) can be divided in to x.y such that x R1 and y R2.
reverse(x.y) = reverse(y).reverse(x), so reverse(L(R1.R2)) = reverse(L(R2)).reverse((L(R1))

L(R2^r).L(R1^r) = L(R2^r.R1^r)

Star: R1^*

reverse(R1^*) = (reverse(R1))^* = (R1^r)^*

Power: R1^k

reverse(R1^k) = (reverse(R1))^k = (R1^r)^k

Hence any regular expression can be broken down in to pieces shown above and we can construct the regular expression for the reverse of a language. Hence that reverse language is also regular.