2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think this is a duplicate of my older question. Do you agree? $\endgroup$ – Raphael May 26 '16 at 20:33
  • $\begingroup$ 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? $\endgroup$ – lukas.coenig May 27 '16 at 5:13
4
$\begingroup$

No. In NPDAs, you can have cycles of $\varepsilon$-transitions that add symbols to the stack. Thus the stack content can be unbounded.

Proving that CFL ⊆ CSL via automata is tough; the trusted route via grammars seems advised.

$\endgroup$
  • $\begingroup$ 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 ... $\endgroup$ – Vor May 26 '16 at 22:50
  • $\begingroup$ @Vor Knowing that every CFL has a Greibach normal form, the standard textbook construction yields an NPDA with linearly bounded stack (iirc). The existence of such an NPDA for every CFL is therefore not surprising, but it's completely unclear (to me) how to get there (more easily than Zetzsche's technique, which I can not claim to fully grasp anyway) directly from an arbitrary NPDA. $\endgroup$ – Raphael May 26 '16 at 23:03
  • 1
    $\begingroup$ I wanted to avoid the detour over grammers as my students at this point don't know them yet. But I get now that it's not a good idea... ;-) $\endgroup$ – lukas.coenig May 27 '16 at 5: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.