Don't understand closure under string reversal

Question

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function,

I having breaking down the syntax to english, my attempt it

for the function delta'' for a given state q and a symbol t the r inside the original set of states Q such that the state q exists in the modified function (in which all final states go to one final state via e-transition) ...

This is where I get confused, its sending r to the modified function delta' but I dont understand what the r stands for and how it comes to be. Furthermore I don't know what Sigma_epsilon means, I assume its the alphabet union with {e}

I also don't see how the induction proof is trivial or easy

Answer 1

Both $q$ and $r$ are states in this construction. If in original $\delta'$ we can step $r\stackrel{t}{\rightarrow} q$ then in the new $\delta''$ we can step $q\stackrel{t}{\rightarrow} r$. Like stated in the proof the arrows are reversed.

You are right, $\Sigma_\epsilon$ is $\Sigma$ plus the empty word $\epsilon$. The original automaton initially has no $\epsilon$-transitions. However it has multiple final states, and after reversing it would have multiple initial states. A possible solution is given here, using $\epsilon$-transitions, connecting a new final state from the original final ones. This is the first step, from $\delta$ to $\delta'$.

If you are still trying to decipher the construction then of course the induction is not trivial. Once you see the arrows are just reversed, then it is not hard to come up with a possible induction assumption: if I can go from $q$ via string $w$ to $r$ in $\delta'$, then I can go from $r$ via string $w^R$ to $q$ in $\delta''$. Then it is no longer difficult. It would not say "easy" as that depends on your experience with induction.