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.
  • 5
    $\begingroup$ The stack language of a PDA is a regular language. $\endgroup$
    – Sylvain
    Sep 10 '12 at 18:00
  • 6
    $\begingroup$ See Context-Free Languages and Pushdown Automata, Theorem 5.3 for the proof. $\endgroup$ Sep 10 '12 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
    Nov 3 '19 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.