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:
- Tried to take up an example, say $E_{1} = 01^{*}$
- Draw an NFA that accepts the regular expression $E_{1}$
- Draw AN NFA that accepts the Kleene's closure of $E_{1}$, i.e. $E = E_{1}^*$
- Convert the NFA into a DFA, and reverse the DFA into an NFA to get $E^{R}$.
- Reduce the NFA of step 4 to a DFA again.
This is my work regarding the same:(Get $E$ as $E^{*}_{1}$)
Now for the right hand side, i.e. $(E^{R}_{1})^*$,
- Created an NFA that accepts $E_{1}$ and reducing it to DFA
- Created an NFA that accepts $E_{1}^{R}$ by reversing
- 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?