This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser.

The transition is defined as $$ \delta: Q\times \Sigma_\varepsilon \times \Gamma_\varepsilon \to P(Q\times \Gamma_\varepsilon) $$ where $Q$ is the set of states, $\Sigma = \Sigma_\varepsilon\cup \varepsilon$ is input alphabets, and $\Gamma_\varepsilon = \Gamma_\varepsilon\cup \varepsilon$ is the stack alphabets.

I think $\Gamma_\varepsilon$ in the co-domain of the transition should be replaced with $\Gamma_\varepsilon^*$; otherwise, I don't see how this definition can pop/push from/onto its stack.

Please help me clarify this.


1 Answer 1


The addition of $\epsilon$ to the alphabets allows the pop and push operations. For example, if you want to push the letter $a$ in state $q$, without reading anything from the input, you can have the transition $\delta(q,\epsilon,\epsilon)=\{(s,a)\}$, where $s\in Q$.

And if you want to pop $a$ without reading anything from the input, you can have $\delta(q,\epsilon,a)=\{(s,\epsilon)\}$.

Of course you can combine the two for a simultaneous pop/push, and you can do that while reading from the input.


Your Answer

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

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