Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which starts with an empty stack and ends with an empty stack and which has the additional property that during this computation, the stack size can increase, but once the stack size decreases it cannot subsequently increase. I want to show that there is a CFG equivalent to $P$ with the property that for each production in this grammar, there is at most one variable on its right-hand side.

My initial idea to approach this problem was to convert $P$ into an equivalent PDA $P'$ which either pops or pushes on every transition, but never both, which empties the stack before accepting, and which has a single final state. Then I would convert $P'$ into a CFG $G'$ using the standard method, as seen here. Finally, I could show that for every $\sigma \in L(P') = L(P)$, there exists a derivation of $\sigma$ in $G$ such that every production applied in this derivation is of the form $A_{pq} \rightarrow aA_{rs}b$, where $p,q,r,s$ are states in $P'$ with the property that a transition exists from $p$ to $r$ which reads input symbol $a$ and pushes a symbol $u$ onto the stack and a transition exists from $s$ to $q$ which reads input symbol $b$ and pops $u$. However, I don't know how to show this to be the case.

  • $\begingroup$ You can always simulate "replace top stack symbol by a string" with a sequence of moves pushing one symbol at a time while reading $\epsilon$ from the input, so this doesn't restrict the language at all. $\endgroup$
    – vonbrand
    Mar 30 '16 at 15:54

In other words, you are constructing a linear grammar for a one-turn pushdown automaton.

So the standard construction from the link (which is Sipser style, afaik) gives productions $A_{ik}\to a A_{\ell j} b$ for each pop-push pair in the computation. That is ok, the productions are of the right form.

Now there are two problems. One is what to do with the zillions of $A_{ij}\to A_{ik}A_{kj}$ productions (which are obviously not allowed!) ? The answer is in the intuitive meaning of the symbols $A_{ij}$.

The second problem is hidden, and not clear in your question (and also not in the example you link). Is it allowed to replace to topmost stack symbol by another (this will not change the stack size) or are those considered two consecutive operations? (Here the Sipser model deviates from the standard one). Also: can we make a computational step. not changing the stack?

  • $\begingroup$ The given PDA $P$ is permitted to simultaneously pop and push a symbol/symbols. That is, $P$ is permitted to have transition labels of the form $a, u \rightarrow v$, where $a \in \Sigma_\varepsilon$ and $u$ and $v$ are stack symbols. According to Sipser's definition (the one I'm using), this amounts to replacing the topmost stack symbol (in this case $u$) by another ($v$ in this case). $\endgroup$ Mar 30 '16 at 1:54
  • $\begingroup$ That is reasonable, but not allowed in the standard construction you link to. It seems one needs a separate idea to get rid of sequences of those transitions. But it can be done... $\endgroup$ Mar 30 '16 at 2:01

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.