Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does havingf(qi, 1, 0)       -> (qj, 0)f(qi, epsilon, 0) -> (qj, 0)cause nondeterminism?I would understand that if I hadf(qi, 1, 0) -> (qj, 0)f(qi, 1, 0) -> (qz, 0)it would cause nondeterminism, because looking at the same input symbol I can choose to move to either qj or qz, that's nondeterminism to me. However the former doesn't make sense at all... This is what Michael Sipser says in his book.
Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?
finite automata;pushdown automata;nondeterminism
Nondeterminism, means the machine has a choice. In both your examples, it indeed has a choice. Let's assume the stack has an 1 on its top, and the next input symbol is 0.The PDA can choose whether to take the transition $f(q_i,1,0)\to(q_i,0)$ or  $f(q_i,\epsilon,0)\to(q_i,0)$. Note that the effect is different: in the first it deletes the 1 in the stack and puts a 0 instead of it. In the second it adds a 0 on top of the 1 without removing it. Therefore, there are two (different) paths the machine can go from this points, hence the nondeterminism.Just to clarify: the definition for Deterministic-PDA is clear-cut: at any moment, and for any input/stack/state configuration there is only one possible transition. If this is not the case, the PDA is non-deterministic even if multiple transitions lead to the same configuration. It's just a matter of definition. However, in the question above, the two transitions may actually lead to different configurations, which makes the nondeterminism even more clear. 