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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.