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.
$\endgroup$

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.