# How do I show that whether a PDA accepts some string w is decidable? or undecidable?

Currently studying for an Automata Theory final and can't find an answer to this question anywhere.

Can you simply let w = w!w and show that it is undecidable that way? Like this here: How do I show that whether a PDA accepts some string $\{ w!w \mid w \in \{ 0, 1 \}^*\}$ is undecidable?

Or do I have to show decidability for arbitrary string w.

Thanks

• There is a difference between a single string "decide whether a given string $w$ is accepted" and a pattern "decide whether any string of the form $w!w$ is accepted". – Hendrik Jan May 3 '17 at 17:40

Given a PDA and a string $w$, there are several algorithms that decide whether the PDA accepts $w$. In fact, for a fixed PDA, such algorithms run in time $O(|w|^3)$ or less. The most well-known algorithm is the CYK algorithm. Although CYK expects the language in the form of a context-free grammar rather than in the form of a PDA, there is an algorithm that converts a PDA to a context-free grammar generating the same language.