In general, the idea for simulation a turingmachine using a PDA with two stacks, is to use one stack representing the already read input and the second stack representing the unread part of the input. To do so we need to read the complete input into one of the stacks. If we use a nondeterministic PDA we are able to read the input and put it on stack 1 and guess the end of the input in order to change state, copying stack 1 to stack 2 in reverse order and to start the simulation.

My question is, how can we archieve a simulation using a deterministic PDA with two stacks? Especially, how do we recognize the end of the input in order to reverse it and to start the simulation. The only way I came up so far, is to demand a special character $ that marks the end of the input.

  • $\begingroup$ You can ask the same about a Turing machine. The input convention on a Turing machine is that the input tape is blank except for the input. A reasonable input convention in your case is what you said. $\endgroup$ – Yuval Filmus May 31 '18 at 19:51

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.