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?

Improve this question
$\endgroup$
2
  • $\begingroup$ I think this is a duplicate of my older question. Do you agree? $\endgroup$
    – Raphael
    Commented May 26, 2016 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
    Commented May 27, 2016 at 5:13

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented May 26, 2016 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
    Commented May 26, 2016 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
    Commented May 27, 2016 at 5:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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