Given a PDA $P$, I believe we can simulate it with a turing machine with 2 tapes - one for keep reading the input and one for the stack.

But, a PDA transition function may have multiple transitions for a given state, letter, and the stack top (the non-deterministic part, or splitting). How can we deal with that in a turing machine?

  • $\begingroup$ List all the transitions like a queue, do the first transition and put it to end, next transition and again put it to the end. Understood? $\endgroup$ Dec 19, 2017 at 9:31
  • $\begingroup$ Not quite. I need to mimic the stack for each transition, which means I need a tape for each transition. Am I correct? Also, I can't mimic each transition separably because one might not end while another might accept. $\endgroup$
    – galah92
    Dec 19, 2017 at 9:32
  • $\begingroup$ I am not sure about what you meant but I will explain what I meant. You can store the entire stack and everything, which we call the configuration of PDA, as a huge string in your TM. Now suppose you have 3 transition. You do the first transition and add it to end of queue, 2nd add it to queue and same with 3rd. Then you dequeue the state you were in and start working on the next configuration your TM has stored in queue. Are we on the same page? $\endgroup$ Dec 19, 2017 at 9:37
  • $\begingroup$ I understand what you're saying. My claim is that each transition need his own copy of stack. How can I save that? $\endgroup$
    – galah92
    Dec 19, 2017 at 9:41
  • $\begingroup$ It is a Turing Machine with infinite tape. You just save the entire stack every time. So you might have 50 copies of the stack(with small changes) in your queue. $\endgroup$ Dec 19, 2017 at 9:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.