Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string.
But are there languages where given an NPDA description as input, the TM may not halt, i.e. since the simulated NPDA also does not halt...
The (non)halting condition for PDAs doesn't make much sense; "non-halting" for a PDA means that there are one or more $\epsilon$-moves (not input read) that can cause a "loop" or an infinite stack expansion.
In order to test if a PDA accepts a string $x$, a Turing machine should not "barely simulate" it (i.e. recusively enumerate all reachable (partial input,stack content,state) configurations of the PDA. Otherwise such machine could never end if the PDA doesn't accept the string and it contains $\epsilon$-moves.
In order to test if a PDA accepts $x$ it you should build the equivalent CFG anc check if the CFG generates the string $x$.
Also note that for any PDA $A$ there is an equivalent (costructible) PDA $A'$ with no $\epsilon$-moves (real-time PDA, i.e. the PDA reads a letter from its input every step) and even there is an equivalent $A''$ with no $\epsilon$-moves and only one state (simple real-time PDA). See Greibach normal form.
A TM once constructed $A'$ (or $A''$) can barely simulate it, enumerating all the possible nondeterministic choices, but in this case it will surely halt.
Transform your PDA into a CFG (standard construction; huge grammar but finite), rewrite the CFG in Chomsky Normal Form (standard construction; again, large grammar but finite process), use CYK algorithm (cubic in input length) with the result.
