# Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?

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 having

f(qi, 1, 0)       -> (qj, 0)
f(qi, epsilon, 0) -> (qj, 0)


cause nondeterminism?

I would understand that if I had

f(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.

## 1 Answer

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.

• f(qi, 1, 0) means it sees 1 in the input string, and 0 on top of the stack, and you wrote it the other way around. So I still don't see any nondeterminism, nondeterminism is defined by being able to move to several different states when seeing the same symbol in the input string. – Pavel Dec 28 '14 at 17:05
• it doesn't matter. In this case, in one case it consumes one symbol of the input, and in the other it doesn't. Still two different paths. – Ran G. Dec 28 '14 at 17:06
• Ah, okay, sorry, that makes sense now, thanks. I was just confused about the epsilon I guess. – Pavel Dec 28 '14 at 17:08
• So, basically there's an infinite amount of epsilons between any 2 characters of the input string and we can either read them or ignore them? – Pavel Dec 28 '14 at 17:10
• exactly! epsilons can be used or ignored at will. – Ran G. Dec 28 '14 at 17:11