# Characterizing a CFG equivalent to a special type of PDA

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.

• 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. Mar 30 '16 at 15:54

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 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). Mar 30 '16 at 1:54