<p>In the standard <span class="math-container">$\epsilon$</span>-free PDA definition the transition function is:</p>

<p><span class="math-container">$\sigma : Q \times \Sigma \times \Gamma \to Q \times \Gamma^*$</span></p>

<p><span class="math-container">$(q_i, a, A, q_j, \alpha) \in \sigma$</span> means that the PDA on state <span class="math-container">$q_i$</span>, with head on input <span class="math-container">$a$</span> and <span class="math-container">$A \in \Gamma$</span> on top of the stack, enters state <span class="math-container">$q_j$</span> and <em>replace</em> <span class="math-container">$A$</span> with <span class="math-container">$\alpha \in \Gamma^*$</span></p>

<p>According to this definition, if <span class="math-container">$|\alpha| \leq 1$</span> there is no way to increase the stack and the resulting automata is a DFA.</p>

<p>But letting <span class="math-container">$|\alpha| \leq 2$</span> is enough to recognize all CFLs; and this is a direct consequence of the following theorem:</p>

<p><strong>Theorem</strong> [D.J. Rosenkrantz. Matrix equations and normal forms for context-free grammars] Given a proper context-free grammar <span class="math-container">$G$</span>, an equivalent context free grammar in <em>quadratic Greibach normal form</em> can effectively be constructed from <span class="math-container">$G$</span></p>

<p>A grammar <span class="math-container">$G$</span> in quadratic Greibach normal form if every right side of the rules is in the form <span class="math-container">$A V^*,\; |V| \leq 2$</span> (<span class="math-container">$A$</span> is the terminal alphabet, <span class="math-container">$V$</span> is the set of non-terminals):</p>

<p><span class="math-container">$X \to a\, B C$</span> or<br>
<span class="math-container">$X \to a\, B$</span> or<br>
<span class="math-container">$X \to a$</span> </p>

<p><span class="math-container">$B, C \in V$</span></p>

<p><strong>***ADDENDUM</strong></p>

<p>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.</p>

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

<p>In order to build an equivalent <span class="math-container">$P'$</span>, we expand the set of non-terminals <span class="math-container">$\Gamma$</span> of <span class="math-container">$P$</span> to <span class="math-container">$\Gamma' = \Gamma \times (\Gamma \cup \{ = \})$</span>; we also expand the set of states <span class="math-container">$Q$</span> to <span class="math-container">$Q' = Q \times (\Gamma \cup \{*\})$</span></p>

<p>The double symbols in each "register" <span class="math-container">$r$</span> of the stack are used to store both the symbol at <span class="math-container">$r$</span> (left element) and to "override" the symbol at <span class="math-container">$r-1$</span> (right element):</p>

<pre><code>      &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
      ....                               ....
</code></pre>

<p>If <span class="math-container">$P'$</span> is in state <span class="math-container">$\langle q_j,*\rangle$</span> 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 <span class="math-container">$\langle q_j, A \rangle$</span> then the "logic" top of the stack is <span class="math-container">$A$</span> (and the real top should be ignored). </p>

<p>So the replace (ii) operation of <span class="math-container">$P$</span> can simply be stored in the internal state of <span class="math-container">$P'$</span>:</p>

<p><span class="math-container">$q_i, a, A \to q_j, B$</span> becomes</p>

<ul>
<li><span class="math-container">$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, B \rangle, \langle A,\cdot\rangle$</span></li>
<li><span class="math-container">$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j,  B \rangle, \langle \cdot,\cdot\rangle $</span></li>
</ul>

<p>As soon as <span class="math-container">$P$</span> needs to PUSH <span class="math-container">$BC$</span> (iii), it can store <span class="math-container">$B$</span> in the right part of the pushed symbol (the "override" part):</p>

<p><span class="math-container">$q_i, a, A \to q_j, BC$</span> becomes</p>

<ul>
<li><span class="math-container">$\langle q_i, * \rangle, a, \langle A,\cdot\rangle \to \langle q_j, * \rangle, \langle A,\cdot\rangle \langle C,B\rangle$</span></li>
<li><span class="math-container">$\langle q_i, A \rangle, a, \langle \cdot,\cdot\rangle \to \langle q_j, * \rangle, \langle \cdot,\cdot\rangle \langle C,B\rangle $</span></li>
</ul>

<p>The <span class="math-container">$P$</span> POP operation (i) can be simulated popping the current top and if it "overrides" the previous element, store it in the state:</p>

<p><span class="math-container">$q_i, a, A \to q_j, \epsilon$</span> becomes</p>

<ul>
<li><span class="math-container">$\langle q_i, * \rangle, a, \langle A,= \rangle \to \langle q_j, * \rangle, \epsilon$</span></li>
<li><span class="math-container">$\langle q_i, * \rangle, a, \langle A,B \rangle \to \langle q_j, B \rangle, \epsilon$</span></li>
<li><span class="math-container">$\langle q_i, A \rangle, a, \langle \cdot,= \rangle \to \langle q_j, * \rangle, \epsilon$</span></li>
<li><span class="math-container">$\langle q_i, A \rangle, a, \langle \cdot,B \rangle \to \langle q_j, B \rangle, \epsilon$</span></li>
</ul>

<p><strong>***ADDENDUM 2</strong></p>

<p>The above proof could be <em>highly simplified</em>, because:</p>

<ul>
<li>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);</li>
<li><span class="math-container">$P'$</span> could simply store the TOP of the stack in its internal state (there is no need to use <span class="math-container">$\Gamma' = \Gamma \times Gamma$</span></li>
</ul>

<p>as soon as I have some free time I'll update the answer.</p>

CC BY-SA 4.0
2019-09-24T15:32:52.163Z
Thanks for your answer, but in my interpretation this would mean two pushes. I tried to make the question more clear.
domotorp
CC BY-SA 4.0
2019-09-24T15:50:15.717Z
@domotorp: Uhm, it seems that according to your interpretation $|\alpha| = 2$ means one push (because in my interpretation it has alreay popped a symbol to decide the transition). In my interpretation a PDA built from a quadratic Greibach normal form grammar (1:1 construction) can : POP or POP PUSH or POP PUSH PUSH.
Marzio De Biasi
CC BY-SA 4.0
2019-09-24T16:09:34.013Z
Perhaps I understood the point: in your interpretation every rules (corresponding grammar) would be of the form $X\to aXB1$ or $X\to X$ or $X\to a$ ... let me think about it.
Marzio De Biasi
CC BY-SA 4.0
2019-09-24T18:57:23.827Z
I think that in your terminology I want to allow only POP or PUSH or POP PUSH. In fact, if you POP PUSH, then I want you to PUSH back the POPPED element, but I can relax this part.
domotorp
CC BY-SA 4.0
2019-09-24T22:17:03.683Z
@domotorp: perhaps I had an idea, see if it is ok (probably not ... :-)
Marzio De Biasi
CC BY-SA 4.0
2019-09-25T07:28:09.250Z
I think there's a typo: in front of '⟨C,B⟩' there shouldn't be another <..> (twice).
domotorp
CC BY-SA 4.0
2019-09-25T07:30:17.287Z
When you deal with $q_i, a, A \to q_j, BC$, shouldn't you also consider the case $\langle q_i, * \rangle, a, \langle A,D\rangle$? I don't see how to deal with that.
domotorp
CC BY-SA 4.0
2019-09-25T07:45:13.920Z
@domotorp  the $\langle A, D \rangle$ remains unchanged (so there is no need to "propagate" $D$). The new stack is $(bottom) [... \langle A, D \rangle \langle C,B \rangle] (top) $.  I just added an end-note that $P'$ could simply store in its internal states the current top of the stack (a sort of "delayed" PUSH)...
Marzio De Biasi
CC BY-SA 4.0
2019-09-25T09:13:06.180Z
I got convinced that this works. I don't think that you need $\Gamma\times\Gamma$, it is enough to push the original non-terminals. The only trick is to 'keep' the top of the stack in mind instead of putting it on the stack. Then using Greibach we need at most one stack operation (POP or PUSH) in each step.
domotorp
CC BY-SA 4.0
2019-09-24T15:00:25.400Z
2019-09-25T07:41:00.650Z
2019-09-25T07:41:00.650Z
Marzio De Biasi
<p>It is known that PDAs without <span class="math-container">$\epsilon$</span> 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?</p>

<p>To be more specific, call a PDA <em>real-time</em> 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.</p>

<blockquote>
  <p>Is there a CFL that no real-time PDA can recognize?</p>
</blockquote>

<p>Related: <a href="https://cstheory.stackexchange.com/questions/32271/are-dpdas-without-a-epsilon-moves-as-powerful-as-dpdas-with-them">Are DPDAs without a $\epsilon$ moves as powerful as DPDAs with them?</a></p>

<p>Crossposted: <a href="https://cs.stackexchange.com/questions/114995/pdas-without-%ce%bb-steps-or-popping-more-than-one-from-stack">https://cs.stackexchange.com/questions/114995/pdas-without-%ce%bb-steps-or-popping-more-than-one-from-stack</a></p>

CC BY-SA 4.0
2019-09-23T22:55:34.003Z
Each PDA has an equivalent that operates in real-time and without epsilon moves (just use Greibach normal form of the corresponding CF grammar). If for "one push or pop move" you mean push or pop just one symbol, then without epsilon moves it cannot even recognize $a^{2n}b^n$
Marzio De Biasi
CC BY-SA 4.0
2019-09-24T05:31:09.153Z
@Marzio Why? Upon reading one $a$, go to state 'read one $a$'. After reading another 'a', go to normal state and push an $a$. So just push every second 'a'.
domotorp
CC BY-SA 4.0
2019-09-24T10:06:59.023Z
Uhm you're right. Trickier than it seems!
Marzio De Biasi
CC BY-SA 4.0
2019-09-24T15:09:47.547Z
I tried a full answer, let me know if I interpreted correctly your question.
Marzio De Biasi
CC BY-SA 4.0
2019-09-24T22:43:41.153Z
Note that your definition of real-time PDA slightly differs from the standard definition (no $\epsilon$ moves)
Marzio De Biasi
<automata-theory><context-free>
Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?
domotorp
# Are PDAs without ϵ moves and with bounded stack operation as powerful as PDAs with them?

(Asked by: username_0 on 2019-09-23)

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?](https://cstheory.stackexchange.com/questions/32271/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>

**Tags:** automata-theory, context-free
> **Comments:**
> **username_1**: Each PDA has an equivalent that operates in real-time and without epsilon moves (just use Greibach normal form of the corresponding CF grammar). If for "one push or pop move" you mean push or pop just one symbol, then without epsilon moves it cannot even recognize $a^{2n}b^n$  
> **username_0**: @Marzio Why? Upon reading one $a$, go to state 'read one $a$'. After reading another 'a', go to normal state and push an $a$. So just push every second 'a'.  
> **username_1**: Uhm you're right. Trickier than it seems!  
> **username_1**: I tried a full answer, let me know if I interpreted correctly your question.  
> **username_1**: Note that your definition of real-time PDA slightly differs from the standard definition (no $\epsilon$ moves)  

---

## 1 answers

### Answer by username_1 on 2019-09-24. Score: 2 | Accepted answer

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

        in P' is equivalent in P to  A
                                     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.

> **Comments:**
> **username_0**: Thanks for your answer, but in my interpretation this would mean two pushes. I tried to make the question more clear.  
> **username_1**: @domotorp: Uhm, it seems that according to your interpretation $|\alpha| = 2$ means one push (because in my interpretation it has alreay popped a symbol to decide the transition). In my interpretation a PDA built from a quadratic Greibach normal form grammar (1:1 construction) can : POP or POP PUSH or POP PUSH PUSH.  
> **username_1**: Perhaps I understood the point: in your interpretation every rules (corresponding grammar) would be of the form $X\to aXB1$ or $X\to X$ or $X\to a$ ... let me think about it.  
> **username_0**: I think that in your terminology I want to allow only POP or PUSH or POP PUSH. In fact, if you POP PUSH, then I want you to PUSH back the POPPED element, but I can relax this part.  
> **username_1**: @domotorp: perhaps I had an idea, see if it is ok (probably not ... :-)  
> **username_0**: I think there's a typo: in front of '⟨C,B⟩' there shouldn't be another <..> (twice).  
> **username_0**: When you deal with $q_i, a, A \to q_j, BC$, shouldn't you also consider the case $\langle q_i, * \rangle, a, \langle A,D\rangle$? I don't see how to deal with that.  
> **username_1**: @domotorp  the $\langle A, D \rangle$ remains unchanged (so there is no need to "propagate" $D$). The new stack is $(bottom) [... \langle A, D \rangle \langle C,B \rangle] (top) $.  I just added an end-note that $P'$ could simply store in its internal states the current top of the stack (a sort of "delayed" PUSH)...  
> **username_0**: I got convinced that this works. I don't think that you need $\Gamma\times\Gamma$, it is enough to push the original non-terminals. The only trick is to 'keep' the top of the stack in mind instead of putting it on the stack. Then using Greibach we need at most one stack operation (POP or PUSH) in each step.  

---

