Can you pop 2 elements at a time in a PDA

In the usual definition of pushdown automata, at every step the PDA pops a stack symbol and reads an input symbol, and based on that it pushes a string of symbols (zero or more) onto the stack, and transitions to a new state (possibly non-deterministically, i.e. there could be several or no choices). If you define PDAs according to this definition then you cannot pop two stack symbols in a single transition.

That said, you can simulate popping two symbols using epsilon transitions (exercise). Therefore, the variant of PDAs in which you are allowed to pop more than one stack symbol is equivalent in power to a standard PDA.

In order to find the answer, one must consult the definition of a pushdown automaton. In general, one should always go back to the definitions when in doubt.

According to the definition in Sipser's popular textbook (https://www.goodreads.com/book/show/400716.Introduction_to_the_Theory_of_Computation) a pushdown automaton is a 6-tuple $(Q,\Sigma,\Gamma,\delta,q_0,F)$ where

• $Q$ is a finite set of states
• $\Sigma$ is the input alphabet
• $\Gamma$ is the stack alphabet
• $\delta$ is the transition function
• $q_0$ is the start state, where $q_0 \in Q$
• $F$ is a set of final states, where $F \subseteq Q$

For the transition function we require that

$$\delta : Q \times \Sigma_{\varepsilon} \times \Gamma_{\varepsilon} \rightarrow \mathcal{P}(Q \times \Gamma_{\varepsilon}$$

where $\Gamma_{\varepsilon}$ denotes the set $\Gamma \cup \{ \varepsilon \}$ and $\Sigma_{\varepsilon}$ denotes the set $\Sigma \cup \{ \varepsilon \}$.

So a clause in the definition of $\delta$ will be of the form

$$\delta(q,x,y) = \{ (q_1,y_1), \ldots, (q_k,y_k) \} \quad \text{where } k \geq 0 $$

($k=0$ means that the set on the right-hand side is empty.)

and is to be read as follows:

Given a state $q$, an $x$ which can be an next input symbol or the empty string and an $y$ which can be the topmost stack symbol or the empty string, the PDA has $k$ possible next moves. In move no. $i$, the PDA replaces $y$ by $y_i$.

If $x = \varepsilon$, this is interpreted as a move that does not involve reading an input symbol. If $y = \varepsilon$, this is interpreted as a move that does not involve reading the top symbol on the stack. If $y_i = \varepsilon$ and $y \neq \varepsilon$, this means that the topmost stack symbol is popped. If $y = \varepsilon$ and $y_i \neq \varepsilon$, this means that $y_i$ is pushed.

Summing up, a pushdown automaton can in a single move

• replace the top stack symbol by another, or
• pop the top stack symbol, or
• push a new stack symbol onto the stack

If you are using jflap, it will allow you to pop two stack items in just one transition. Theoretically, it is more logical to pop one item from the stack one item at a time