2
$\begingroup$

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.

From Sipser's Theory of Computation

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Evil Jul 12 '19 at 23:51
  • $\begingroup$ Due to epsilon transitions, there‚Äôs no obvious upper bound on the number of steps that the PDA executes. $\endgroup$ – Yuval Filmus Jul 13 '19 at 0:06
  • $\begingroup$ @Evil What I overlooked was that PDA's can't recognize all context free languages...only the deterministic ones. $\endgroup$ – Eesh Starryn Jul 15 '19 at 21:29
2
$\begingroup$

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!).

Why is this a problem? Consider a deterministic Turing machine which runs all possible computations of the PDA, accepting if it finds an accepting computation, and rejecting otherwise. If there is no computable upper bound on the length of a computation, then the Turing machine will have to try infinitely many computations in the rejecting case, and so won't halt on rejecting inputs.

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.

| cite | improve this answer | |
$\endgroup$

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