# 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?

• 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$ Sep 23, 2019 at 22:55
• @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'. Sep 24, 2019 at 5:31
• Uhm you're right. Trickier than it seems! Sep 24, 2019 at 10:06
• I tried a full answer, let me know if I interpreted correctly your question. Sep 24, 2019 at 15:09
• Note that your definition of real-time PDA slightly differs from the standard definition (no $\epsilon$ moves) Sep 24, 2019 at 22:43

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$$

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$$

• $$P'$$ could simply store the TOP of the stack in its internal state (there is no need to use $$\Gamma' = \Gamma \times Gamma$$
• @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. Sep 24, 2019 at 15:50
• 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. Sep 24, 2019 at 16:09