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.
I hope this helps $\ddot\smile$