3
$\begingroup$

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? enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – sashas Oct 15 '15 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$ – Yuval Filmus Oct 15 '15 at 20:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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