# When does a PDA split?

In case of NFA, if the NFA is in a state and reads $\epsilon$ ( empty string ) the NFA splits in to two, with one being at the current state and other with the state along the $\epsilon$ transition. In case of PDA where transitions are of the type $a,b \to c$, with $a$ being the input alphabet being read, $b$ being the stack element being read and popped and $c$ being the stack element being pushed. In NFA I understood the splitting upon $\epsilon$ as the ability to guess. So I assumed that a PDA in a state $r$ with stack being $S$ splits into two PDA only when the transition is $\epsilon,\epsilon \to \epsilon \\$ ( that is when $a=b=c=\epsilon$ in the figure below the PDA splits into two with one being in state $r$ and other in $s$ with same stack $S$ ). But now I am a bit doubtful, about when does a PDA split. I feel I am wrong and am misunderstanding something trivial. ( The figure below just shows the part of a larger PDA ). How would it affect the power of a PDA if it were only allowed to split on $\epsilon,\epsilon \to \epsilon$ transition?

A PDA (or an NFA) could have more than one possible move even if it has no $\epsilon$ moves, and conversely, there might be situations in which an $\epsilon$ move is the only possible move of the automaton (can you think of such a situation?). So your identifying $\epsilon$ transitions with "splitting" is wrong.
• If there are several options to follow I can always replace it by adding a new state and then using $\epsilon$ transitions, if I am not wrong. So I always understood non-determinism in terms of $\epsilon$ transitions, as I can always achieve the effect of same transition leading to multiple options by $\epsilon$ transitions alone . I am sorry for asking the same thing again and again. But Sipsers explains $\epsilon$ transitions in NFA as splitting NFA into two each following one possibility. – sashas Oct 15 '15 at 20:36
• While you can simulate non-determinism using only $\epsilon$-transitions as "splitting points", it's definitely not the usual point of view. However, whatever works for you is fine, as long as you understand the concepts correctly. – Yuval Filmus Oct 15 '15 at 20:46