Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them? It is known that PDAs without $\epsilon$ moves are as powerful as PDAs with them.
However, it seems to me that the proof allows several stack operations in one move. What happens if we allow at most one push or pop in each move?

To be more specific, call a PDA real-time if the machine can see the currently read letter and the top of the stack, then based on this, it either needs to delete the top element of the stack (pop), or push one element onto the stack (push), or leave the stack as it is. In either case, it has to move to the next letter.


  Is there a CFL that no real-time PDA can recognize?


Related: Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?

Crossposted: https://cs.stackexchange.com/questions/114995/pdas-without-%ce%bb-steps-or-popping-more-than-one-from-stack
In the standard $\epsilon$-free PDA definition the transition function is:

$\sigma : Q \times \Sigma \times \Gamma \to Q \times \Gamma^*$

$(q_i, a, A, q_j, \alpha) \in \sigma$ means that the PDA on state $q_i$, with head on input $a$ and $A \in \Gamma$ on top of the stack, enters state $q_j$ and replace $A$ with $\alpha \in \Gamma^*$

According to this definition, if $|\alpha| \leq 1$ there is no way to increase the stack and the resulting automata is a DFA.

But letting $|\alpha| \leq 2$ is enough to recognize all CFLs; and this is a direct consequence of the following theorem:

Theorem [D.J. Rosenkrantz. Matrix equations and normal forms for context-free grammars] Given a proper context-free grammar $G$, an equivalent context free grammar in quadratic Greibach normal form can effectively be constructed from $G$

A grammar $G$ in quadratic Greibach normal form if every right side of the rules is in the form $A V^*,\; |V| \leq 2$ ($A$ is the terminal alphabet, $V$ is the set of non-terminals):

$X \to a\, B C$ or
$X \to a\, B$ or
$X \to a$ 

$B, C \in V$

***ADDENDUM

This is an idea to prove that even with the constraint required by domotorp in the question (at each step 1 POP or 1 PUSH or NO CHANGES ) we can recognize all CFLs.

The above theorem says that a PDA $P$ that can "look" at the top symbol $X$ of the stack and according to it and the current input symbol can (i) POP it, (ii) REPLACE it with $B$ or (iii) REPLACE it with $B$ and PUSH $C$ is as powerful as a PDA.

In order to build an equivalent $P'$, we expand the set of non-terminals $\Gamma$ of $P$ to $\Gamma' = \Gamma \times (\Gamma \cup \{ = \})$; we also expand the set of states $Q$ to $Q' = Q \times (\Gamma \cup \{*\})$

The double symbols in each "register" $r$ of the stack are used to store both the symbol at $r$ (left element) and to "override" the symbol at $r-1$ (right element):

      &lt;A,B&gt;  in P' is equivalent in P to  A 
      &lt;C,.&gt;                               B
      ....                               ....

      &lt;A,=&gt;  in P' is equivalent in P to  A
      &lt;C,.&gt;                               C
      ....                               ....


If $P'$ is in state $\langle q_j,*\rangle$ it means that the "logic" top of the stack symbol that it should use is effectively the top of the stack; if it is in state $\langle q_j, A \rangle$ then the "logic" top of the stack is $A$ (and the real top should be ignored). 

So the replace (ii) operation of $P$ can simply be stored in the internal state of $P'$:

$q_i, a, A \to q_j, B$ becomes


$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, B \rangle, \langle A,\cdot\rangle$
$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j,  B \rangle, \langle \cdot,\cdot\rangle $


As soon as $P$ needs to PUSH $BC$ (iii), it can store $B$ in the right part of the pushed symbol (the "override" part):

$q_i, a, A \to q_j, BC$ becomes


$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, * \rangle, \langle A,\cdot\rangle \langle C,B\rangle$
$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j, * \rangle, \langle \cdot,\cdot\rangle \langle C,B\rangle $


The $P$ POP operation (i) can be simulated popping the current top and if it "overrides" the previous element, store it in the state:

$q_i, a, A \to q_j, \epsilon$ becomes


$\langle q_i, * \rangle, a, \langle A,= \rangle \to \langle q_j, * \rangle, \epsilon$
$\langle q_i, * \rangle, a, \langle A,B \rangle \to \langle q_j, B \rangle, \epsilon$
$\langle q_i, A \rangle, a, \langle \cdot,= \rangle \to \langle q_j, * \rangle, \epsilon$
$\langle q_i, A \rangle, a, \langle \cdot,B \rangle \to \langle q_j, B \rangle, \epsilon$


***ADDENDUM 2

The above proof could be highly simplified, because:


the PDA derived from the quadratic Greibach Normal form needs only one state (provided that the acceptance condition is the empty stack at the end of the input);
$P'$ could simply store the TOP of the stack in its internal state (there is no need to use $\Gamma' = \Gamma \times Gamma$


as soon as I have some free time I'll update the answer.