1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Pavel
    Dec 28, 2014 at 17:05
  • $\begingroup$ 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. $\endgroup$
    – Ran G.
    Dec 28, 2014 at 17:06
  • $\begingroup$ Ah, okay, sorry, that makes sense now, thanks. I was just confused about the epsilon I guess. $\endgroup$
    – Pavel
    Dec 28, 2014 at 17:08
  • $\begingroup$ 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? $\endgroup$
    – Pavel
    Dec 28, 2014 at 17:10
  • 1
    $\begingroup$ exactly! epsilons can be used or ignored at will. $\endgroup$
    – Ran G.
    Dec 28, 2014 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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