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?
$\begingroup$
$\endgroup$
asked Oct 8, 2015 at 3:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
A PDA (or an NFA) doesn't split. At any given point in time, it non-deterministically chooses a valid next step, if any. If there are several options, you can say that the PDA "splits" if you wish, trying all of them in parallel.
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.
answered Oct 15, 2015 at 20:09
-
$\begingroup$ 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. $\endgroup$ Oct 15, 2015 at 20:36
-
1$\begingroup$ 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. $\endgroup$ Oct 15, 2015 at 20:46