# Is a PDA's stack size linear bounded in input size?

I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. Using only regular transitions, the stack can rise to maximally (more or less) $kn$ symbols in a run on an input sized $n$.

But what about $\epsilon$-transitions? Is there a simple argument why their maximum number should as well be independent of the input size?

So, in short: Is a PDA's stack size linear in the input size?

• I think this is a duplicate of my older question. Do you agree? – Raphael May 26 '16 at 20:33
• Yes, it's fine by me to mark the question as duplicate. Yours is far more specific and covers mine. (PS. I have basically no internet connection due to moving, so I can't really join the discussion; I hope at least this comment will be sent... But thanks a lot for the interesting suggestions. I wouldn't have thought this to be so hard.) Btw. Is it any different for DPDA? – lukas.coenig May 27 '16 at 5:13

No. In NPDAs, you can have cycles of $\varepsilon$-transitions that add symbols to the stack. Thus the stack content can be unbounded.
• I think that if you allow the (bounded) stack size to be a function $f(n)$ of the input length (as Lukas said in the question) and the non-deterministc branches that cause a "stack overflow" are simply discarded, then for each NPDA $A$ there is an equivalent $f_A(n)$-NPDA $A'$ that recognizes the same language (though the function $f$ is probably not linear). I'll search for references ... – Vor May 26 '16 at 22:50