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?