I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why?

I know that a pushdown automaton can use exactly one step per input symbol, which is a tight lower bound on efficiency. (If we’re measuring in number of steps, anyway.) This is better than a single-tape Turing machine can do. But, I think that a Turing machine with an input tape and a working tape can emulate a pushdown automaton directly, using the same number of steps.

So, in the end, which kind of automaton machine promisingly can serve as a recognizer for CFL?? And why?

  • 1
    $\begingroup$ You can simulate a DPDA with a Turing machine very efficiently, and a PDA with a nondeterministic Turing machine as efficiently. $\endgroup$ – Yuval Filmus Feb 5 at 10:27
  • $\begingroup$ So, you vote for turing machine? $\endgroup$ – Tom Feb 5 at 11:51
  • 1
    $\begingroup$ It depends if you want it to be deterministic or not. $\endgroup$ – Yuval Filmus Feb 5 at 12:00
  • $\begingroup$ What about a general view? $\endgroup$ – Tom Feb 5 at 12:07
  • $\begingroup$ The best known deterministic algorithm for accepting general context-free languages runs in matrix multiplication time, and there are time-space tradeoffs for the language of palindromes on single tape Turing machines. $\endgroup$ – Yuval Filmus Feb 5 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.