6
$\begingroup$

Consider a pushdown automaton $A$ with stack alphabet $\Gamma$. Let $L$ be the language on $\Gamma$ of the stack configurations encountered during accepting runs of $A$. Is $L$ a context-free language?

Preliminary observations:

  • $L$ is prefix-closed (any prefix of $L$ is in $L$)
  • Using Bar-Hillel's lemma, pumping on the context-free language amounts to pumping on the stack language like a regular language. Hence, $L$ can be pumped as a regular language.
Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ The stack language of a PDA is a regular language. $\endgroup$
    – Sylvain
    Commented Sep 10, 2012 at 18:00
  • 7
    $\begingroup$ See Context-Free Languages and Pushdown Automata, Theorem 5.3 for the proof. $\endgroup$
    – Marzio De Biasi
    Commented Sep 10, 2012 at 18:39
  • $\begingroup$ @MarzioDeBiasi The link is broken. Could you please provide a new link or the citation if it is a paper? $\endgroup$
    – Rahul Gopinath
    Commented Nov 3, 2019 at 8:33

0

Reset to default

Your Answer

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