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^r describing the language L^r consisting of the reverse of all strings in L.

Solution

You have to show that you can always construct a finite automaton that accepts strings in LRgiven a finite automaton that accepts strings in L. Here is a procedure to do that.

First, we prove the following statement: a path from q to p in A labeled with w if and only if a path from p to q in AR labeled with wR (the reverse of w) for q,pQA. The proof is by induction on the length of w.

Letting q=qA and p=s for some sFA and substituting wRwR for xRa guarantees that pAR(s,wR) sFA. Since there is a path labeled with from qs to every state in FA (3. in the definition of AR) and a path from every state in FA to the state qA labeled with wR, then there is a path labeled with wR=wR from qs to qA. This proves the theorem.

Notice that this proves that (LR)R=L(LR)R=L as well.