5

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

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

1 Answers1

2

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.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
  • Thanks for your answer, but in my interpretation this would mean two pushes. I tried to make the question more clear. – domotorp Sep 24 '19 at 15:32
  • @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 Sep 24 '19 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. – Marzio De Biasi Sep 24 '19 at 16:09
  • 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 Sep 24 '19 at 18:57
  • @domotorp: perhaps I had an idea, see if it is ok (probably not ... :-) – Marzio De Biasi Sep 24 '19 at 22:17
  • I think there's a typo: in front of '⟨C,B⟩' there shouldn't be another <..> (twice). – domotorp Sep 25 '19 at 07:28
  • 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 Sep 25 '19 at 07:30
  • @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 Sep 25 '19 at 07:45
  • 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 Sep 25 '19 at 09:13