here comes a problem for you. It is natural to add an extra stack to a PDA. Say

Question

here comes a problem for you. It is natural to add an extra stack to a PDA. Say M is a two-stack PDA if M is exactly the same as a PDA but with two stacks. Each instruction (transition) in M is in the form of (p gamma_1, gamma_2) delta (q, a, b_1, b_2) which means that if M is at state q and reading input symbol a with the top of the two stacks being b_1 and b_2 respectively, then this transition brings M to state p, and replaces the tops b_1 and b_2 of the two stacks to gamma_1 and gamma_2 respectively. Show (describe) that any Turing machine can be simulated by a two-stack PDA.

Explanation / Answer

The Turing machine can be simulated by a two stack PDA: Take two stacks such that they are being concatenated at their tops. When a symbol which is in the first stack needs to access then we pop all the contents of the first stack above that symbol and we will push the contents to the second stack. In this any symbol can be accessed which is stored in a stack without loosing any contents. Similarly this simulates the tape of a Turing machine where the head corresponds to the heads of the two stacks.
In other words, take two stacks i.e. left and right to hold the tape contents to the left and right of the current head position respectively. The 2-PDA starts by pushing lastmark onto the left and right stacks. Input string then pushes onto the left stack which results to scan the Turing Machine head across the input string. The string is now all to the left of the Turing Machine head. The 2-PDA now pops symbols off of the left stack and pushes them onto the right stack until it reaches the lastmark the 2-PDA stacks set-up to correspond to the Turing Machines tape. The 2-PDA simulates the Turing Machines move: If the Turing Machines moves its head to the left with the current move, then the 2-PDA pops the current symbol off of the right stack and pushes the symbol that the Turing Machines writes onto the right stack while on the other side it pops the current symbol off of the right stack and pushes the symbol that the Turing Machines writes onto the left stack. If on the right than it pushes a blank onto the right stack. If the top-of-stack symbol on the left stack is not a, the 2-PDA pops this symbol off of the left stack and pushes it on the right stack. In this way we can say that Turing Machine can be simulated by a two stack PDA.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.