3
$\begingroup$

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
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – dtldarek
    Aug 6, 2013 at 18:22
  • $\begingroup$ @dtldarek your comment may be suited for an answer, isn't it? $\endgroup$
    – wece
    Aug 13, 2013 at 7:55
  • $\begingroup$ @wece Done. ${}$ $\endgroup$
    – dtldarek
    Aug 13, 2013 at 23:43

1 Answer 1

2
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .