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):
<A,B> in P' is equivalent in P to A
<C,.> B
.... ....
<A,=> in P' is equivalent in P to A
<C,.> 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.
