5
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer, but in my interpretation this would mean two pushes. I tried to make the question more clear. $\endgroup$ – domotorp Sep 24 at 15:32
  • $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Sep 24 at 15:50
  • $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Sep 24 at 16:09
  • $\begingroup$ 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. $\endgroup$ – domotorp Sep 24 at 18:57
  • $\begingroup$ @domotorp: perhaps I had an idea, see if it is ok (probably not ... :-) $\endgroup$ – Marzio De Biasi Sep 24 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.