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.


  • $\begingroup$ 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". $\endgroup$ – 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.

I expect every decent textbook on automata theory to contain a proof that the acceptance problem for PDAs (given a PDA and a string, determine whether it accepts the string) is decidable, say along the lines above.

  • $\begingroup$ You mean after a PDA to CFG conversion? $\endgroup$ – Hendrik Jan May 3 '17 at 17:37
  • $\begingroup$ PDA, CFG, it's all the same. Right, so there is an extra step needed... $\endgroup$ – Yuval Filmus May 3 '17 at 17:38

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.