1
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\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$ – User Not Found Dec 19 '17 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 '17 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$ – User Not Found Dec 19 '17 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 '17 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$ – User Not Found Dec 19 '17 at 9:43

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.