This question already has an answer here:

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable.

I would say that you can simulate a push down automaton with a Turing Machine and, if it doesn't loop forever, accept the word when the automaton accepts, or reject when it does. In this case, the problem of decide if a push down automaton accept a word would be semi-decidable. But I'm not sure if that is correct and also, I can't find a way to prove if it is decidable or not.

Any ideas here?


marked as duplicate by Apass.Jack, Evil, dkaeae, David Richerby, Gilles Jul 5 at 5:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


Pushdown automata are nondeterministic, and there is no a priori bound on the length of computation (imagine $\epsilon$-transitions that add and remove the same element from the stack). Therefore it's not clear how to perform your simulation.

Fortunately, we know how to convert a pushdown automaton to an equivalent context-free grammar, and the latter have parsing algorithms such as CYK. Using these algorithms, we can dedice whether a given pushdown automaton accepts a word by first converting the automaton into a context-free grammar.


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