<p>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?</p>

<p>Preliminary observations:</p>

<ul>
<li>$L$ is prefix-closed (any prefix of $L$ is in $L$)</li>
<li>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.</li>
</ul>

CC BY-SA 3.0
2012-09-10T18:00:13.340Z
The stack language of a PDA is a regular language.
Sylvain
CC BY-SA 3.0
2012-09-10T18:39:25.367Z
See [Context-Free Languages and Pushdown Automata](http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/ENS/Articles/cflpda.ps), Theorem 5.3 for the proof.
Marzio De Biasi
CC BY-SA 4.0
2019-11-03T08:33:30.223Z
@MarzioDeBiasi The link is broken. Could you please provide a new link or the citation if it is a paper?
Rahul Gopinath
<fl.formal-languages><automata-theory><context-free-languages>
Language of stack configurations of a pushdown automaton
Antoine Amarilli 'a3nm'
# Language of stack configurations of a pushdown automaton

(Asked by: username_0 on 2012-09-10)

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.

**Tags:** fl.formal-languages, automata-theory, context-free-languages
> **Comments:**
> **username_1**: The stack language of a PDA is a regular language.  
> **username_2**: See [Context-Free Languages and Pushdown Automata](http://www.liafa.jussieu.fr/~carton/Enseignement/Complexite/ENS/Articles/cflpda.ps), Theorem 5.3 for the proof.  
> **username_3**: @MarzioDeBiasi The link is broken. Could you please provide a new link or the citation if it is a paper?  

---

## 0 answers

