Closure under reversal of regular languages: Proof using Automata

Question

I have been studying the closure properties of regular languages, referencing the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman.

Under the topic of Reversal, they have tried to prove that the regular languages are preserved under the reversal of closure. They have stated the following (for a regular language $E$):

$E = E^{*}_{1}$. Then $E^R = (E^{R}_{1})^*$

I wasn't able to get their justification so I took the following approach:

1. Tried to take up an example, say $E_{1} = 01^{*}$
2. Draw an NFA that accepts the regular expression $E_{1}$
3. Draw AN NFA that accepts the Kleene's closure of $E_{1}$, i.e. $E = E_{1}^*$
4. Convert the NFA into a DFA, and reverse the DFA into an NFA to get $E^{R}$.
5. Reduce the NFA of step 4 to a DFA again.

This is my work regarding the same:

Now for the right hand side, i.e. $(E^{R}_{1})^*$,

1. Created an NFA that accepts $E_{1}$ and reducing it to DFA
2. Created an NFA that accepts $E_{1}^{R}$ by reversing
3. Created an NFA that accepts $(E^{R}_{1})^*$ by taking the Kleene Closure, and then reduced it to a DFA.

This is my work for the second half:

However, the two DFAs I get at the end are not similar. Can anyone help me with the error I might be making?

Plus, how can we prove the same in a way other than DFA/NFA construction?

Answer 1

You are asking two questions. I will only answer the second one. Recall that $L^* = \bigcup_{n=0}^\infty L^n$. I will show that $(L^k)^R = (L^R)^k$, and then it easily follows that $(L^*)^R = (L^R)^*$.

To show that $(L^k)^R = (L^R)^k$, notice that: $$ (L^k)^R = \{ (w_1\ldots w_k)^R : w_1,\ldots,w_k \in L \} = \\ \{w_k^R \ldots w_1^R : w_k,\ldots,w_1 \in L \} = \\ \{z_k \ldots z_1 : z_k,\ldots,z_1 \in L^R \} = (L^R)^k. $$ If you want to be more formal, you can prove this by induction on $k$. The crucial observation is $(xy)^R = y^R x^R$, which you can also prove by induction if you want to be very formal.

Answer 2

A proof using the definitions of the operators, as given by Yuval, is the way I would also approach this. As for the question of possible mistakes in your automata, there are two:

• In the first construction, at the very end you mark state $Z$ as accepting, when it shouldn't be.
• In the second construction, when going from $E^R$ to $(E^R)^*$, you add an $\epsilon$ transition to $B$ from the (non-accepting) state $Y$ rather than from $Z$.