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: Qtimes Sigma_varepsilon times Gamma_varepsilon to P(Qtimes Gamma_varepsilon) $$ where $Q$ is the set of states, $Sigma = Sigma_varepsiloncup varepsilon$ is input alphabets, and $Gamma_varepsilon = Gamma_varepsiloncup 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 $sin 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
