# Formal Reduction: Pushdown Automata recognizing context free languages with bounded stack

I am studying for an exam in automata theory and I am having trouble solving the following:

Consider pushdown automata and context free languages. Show that the following decision problem is undecidable by providing a formal reduction from a known undecidable problem.

Input: A context free language $\mathcal{L}$ given in form of a grammar $\mathcal{G}$.

Question: Is there a push down automaton $\mathcal{P}$ which recognizes $\mathcal{L}$ with bounded stack usage, i.e. there is a bound $k \in \mathbb{N}$ such that no run of $\mathcal{P}$ needs more than $k$ symbols on the stack.

Hint: The decision problem whether a given context free language $\mathcal{L}$ is regular is undecidable.

My thoughts so far:

• If stack is bounded, push down automata can be transformed into an NFA
• NFA recognize regular languages
• Context free languages are not recognizable by bounded pushdown automata
• As you observed, if there exists a stack-bounded automata, then $\mathcal{L}$ is regular. Moreover, NFA is a stack-bounded automaton (with bound being 0), so this is an "if and only if" connection between existence of appropriate stack-bounded automata and NFAs. This way, given an algorithm that solves your problem, you can tell whether a context free language is regular. – dtldarek Aug 6 '13 at 18:22
• @dtldarek your comment may be suited for an answer, isn't it? – wece Aug 13 '13 at 7:55
• @wece Done. ${}$ – dtldarek Aug 13 '13 at 23:43

As you observed, if there exists a stack-bounded automata, then $\mathcal{L}$ is regular. Moreover, NFA is a stack-bounded automaton (with bound being 0), so this is an "if and only if" connection between existence of appropriate stack-bounded automata and NFAs. This way, given an algorithm that solves your problem, you can tell whether a context free language is regular.
I hope this helps $\ddot\smile$