b) A turing machine can simulate a 2-PDA (HINT: Use a multi tape non-deterministic turing machine)

1. A 2-PDA is a push-down automaton with two stacks instead of one. Prove that a 2-PDA is equivalent to a Turing Machine. Note that you will need to prove both of the following A 2-PDA can simulate a Turing Machine. (HINT: To get started, call the stacks the left stack and the right stack. To set up the simulation, begin by pushing "" onto the left and right stacks. Then, push every character in the input string onto the left stack. Then push it onto the right stack. Below is partial transition diagram showing this set-up, where the input alphabet -(0,1) and -(0,1,-} where"-" is the blank character and qTM-start is the start state for the Turing Machine simulation. You do not need to sketch a diagram for the simulation. Just describe the action of the 2-PDA based on the Turing Machine's transition function : Q X -> QX X {L,R). Note that all of the transitions in the simulation will be s-transitions, since the input was completely processed by the setup.) a. , pop every character from the left stack and L: 0->E R: 8-0 L: 0 R: e-> qstart qright-setup qleft-setup QrM-start L: 1>8 R: 8-1 1. A 2-PDA is a push-down automaton with two stacks instead of one. Prove that a 2-PDA is equivalent to a Turing Machine. Note that you will need to prove both of the following A 2-PDA can simulate a Turing Machine. (HINT: To get started, call the stacks the left stack and the right stack. To set up the simulation, begin by pushing "" onto the left and right stacks. Then, push every character in the input string onto the left stack. Then push it onto the right stack. Below is partial transition diagram showing this set-up, where the input alphabet -(0,1) and -(0,1,-} where"-" is the blank character and qTM-start is the start state for the Turing Machine simulation. You do not need to sketch a diagram for the simulation. Just describe the action of the 2-PDA based on the Turing Machine's transition function : Q X -> QX X {L,R). Note that all of the transitions in the simulation will be s-transitions, since the input was completely processed by the setup.) a. , pop every character from the left stack and L: 0->E R: 8-0 L: 0 R: e-> qstart qright-setup qleft-setup QrM-start L: 1>8 R: 8-1