patternMinor
Why can PDAs only write one symbol to the stack according to this definition?
Viewed 0 times
thisdefinitionwhycanthestacksymbolpdaswriteone
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#62396, answer score: 6
Revisions (0)
No revisions yet.