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,

enter image description here

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

  • 1
    $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – FrankW
    Commented Sep 15, 2014 at 8:54
  • $\begingroup$ Related question. $\endgroup$
    – Raphael
    Commented Sep 15, 2014 at 10:53

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.