# To check whether the problem of a particular string being a member of CFG G is decidable or not, why can't we use a PDA? [closed]

Why can't a TM simulate a PDA? Then we can easily construct a PDA P which is made from grammar G. And contruct a TM that simulates P to prove that this problem is decidable.

• You have different question in title and in the body. Why do you think that TM can't simulate PDA? Is something missing in the excerpt pasted? – Evil Jul 12 '19 at 23:51
• Due to epsilon transitions, there’s no obvious upper bound on the number of steps that the PDA executes. – Yuval Filmus Jul 13 '19 at 0:06
• @Evil What I overlooked was that PDA's can't recognize all context free languages...only the deterministic ones. – Eesh Starryn Jul 15 '19 at 21:29

Consider a pushdown automaton which has an $$\epsilon$$-transition which adds $$A$$ to the stack, and another $$\epsilon$$-transition that removes $$A$$ from the stack. Clearly, this PDA has accepting computations of unbounded length. There is no a priori bound on the shortest computation needed to accept a string of a certain length (though perhaps you can come up with such a bound if you're smart enough!).
The same problem occurs with context-free grammars having unit productions (consider for example a grammar with the productions $$A\to B$$ and $$B\to A$$). After removing unit productions and $$\epsilon$$-productions, the problem goes away, and you can use dynamic programming to decide the language of the context-free grammar. This is (essentially) the CYK algorithm.