2
$\begingroup$

According to my book the definition of a deterministic Pushdown automaton allows for $\delta(q,\epsilon,Z)$ to be non-empty if $\forall\sigma\in\Sigma:\,\delta(q,\sigma,Z)\neq\emptyset$

Can someone please explain/give motivation for this definition ?

Mainly, why is the automaton deterministic if we allow $\epsilon$ movements ? why do we condition it on the (strange) condition that $\forall\sigma\in\Sigma:\,\delta(q,\sigma,Z)\neq\emptyset$ ?

1 Answers 1

3

That looks like a typo: the usual definition is that if $\delta(q,\epsilon,Z)\ne\varnothing$, then $\delta(q,\sigma,Z)$ must be empty for each $\sigma\in\Sigma$, so that there’s no ambiguity.