[Solved]: Why can PDAs only write one symbol to the stack according to this definition?

Problem Detail: 

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.

Asked By : Myath

Answered By : Shaull

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/62396