Implementation details of "transitions" of Non-deterministic push-down automata

Question

I am reading "Introduction to the Theory of Computation" 3rd edition ~ by Michael Sipser, page 113-114 - topic: "Context free languages, push down automata"

He states that the transition from one state to another would look as follows: "$a,b\rightarrow c$". But the way he states the usage confuses me

We write "$a,b \rightarrow c$" to signify that when the machine is reading an $a$ from the input, it may replace the symbol $b$ on the top of the stack with a $c$. Any of $a,b \ and \ c"$ may be $ε$

If $a$ is $ε$, the machine may make this transition without reading any symbol from the input

If $b$ is $ε$, the machine may make this transition without reading and popping any symbol from the stack

If $c$ is $ε$, the machine does not write any symbol on the stack when going along this transition

My question is what would happen in the following cases:

1. When $b$ is $ε$, and $c$ is $ε$
2. When $b$ is $ε$ and $c$ contains a symbol
3. When $b$ contains a symbol and $c$ is $ε$
4. When $b$ contains a symbol and $c$ contains a symbol, where both symbols are different
5. When $b$ contains a symbol and $c$ contains a symbol, where both symbols are same

My understanding is as follows: if $b$ is $ε$ then we "push" a symbol on stack, if $c$ is empty then we "pop" a symbol from the stack and when he says $a,b \rightarrow c$ he means, given $b$ is not $ε$, "if" $b$ is the top symbol of the stack then we can either pop or replace, and my answers to the above questions are as follows:

1. Push operation: Push empty string on stack, meaning make no changes to the stack ( not sure about this one because both $b$ and $c$ are $ε$ so it could be a push + pop operation??, clarify please this especially )
2. Push operation: Push the symbol $c$
3. Pop operation: Pop the top symbol $b$ from the stack
4. Replace operation: Replace the top symbol that is $b$ with $c$
5. Replace operation: Replace the top symbol that is $b$ with $c$, in this case the stack will remain the same

Answer 1

Kindly read again the description you have quoted from the book. It states there that $b$ is the stack element to be read and popped and $c$ would be the symbol to be pushed on top of the stack. So to answer your questions:

1. Nothing will be popped and pushed
2. Nothing will be popped but $c$ will be pushed
3. Pop the stack and push nothing
4. Pop the stack and push $c$
5. Same as 4, as it doesn't matter if you pop and push the same symbol. You can think of this as the PDA inspecting (by popping) the top symbol and decided that this symbol is not yet meant to be popped in the current state, so it simply returned the popped symbol.

Answer 2

The standard/usual/common definition of a push-down automaton allows instructions of the form $(p,a,A,q,\alpha)$ meaning in state $p$ reading $a$ from the input and $A$ on top of the stack, we move to state $q$ and replace $A$ by $\alpha$ on the stack.
Thus, we always combine both a pop $A$ and a push $\alpha$.

There are some special cases.

• The input read can be $a=\varepsilon$, meaning that the input is ignored. The transition can take place whatever is on the input tape.

• We may push $\alpha=\varepsilon$, which means that only top $A$ is popped without replacement, so that is a "pure" pop.

• We may push $\alpha = A$: the symbol on top is returned, and we have only verified that the topmost symbol is indeed $A$.

• If we want to push a string $\gamma$ "on top of" the current $A$ we have to push $A\gamma$ to first return $A$ on the stack.

This definition always first pops a symbol from the stack. That means the PDA is not able to operate on the empty stack. Indeed, the definition of a PDA provides an initial stack symbol $Z$, and we may prefer to keep that on stack until accepting, in order to avoid the empty stack halfway through.

As far as I understand the usual assumption on $A/\alpha$ with nonempty $A$ is to keep the PDA quite similar to context-free grammar which also operates with rules $A\to\alpha$, except that a PDA additionally has states.

One of the few books I know that deviate from this is S*pser, where now $A$ is allowed to be empty, so one may push symbols on the empty stack, without popping. This does not change the power of pushdown automata, except when considering determinism.