Theory of Computation - Turing Machines

Problem 2. 2-stack PDAs We can define a class of 2-stack PDAs (or "2PDA" for short), which have 2 stacks instead of one. On any transition, 2PDAs can push and/or pop either or both stacks. (This is analogous to how multitape TMs can read/write multiple tapes on each transaction) Just as for regular PDAs, both stacks are initially empty (a) Give a formal definition of 2PDA (including of the transitions) (b) What would its configuration consist of? What would be an initial configuration? A final ion (c) Given a current configuration and a transition, how do we compute what the next configuration will be? Hint: look at the definitions of a 2-tape vs. a 1-tape TM for inspiration. Problem 2. 2-stack PDAs We can define a class of 2-stack PDAs (or "2PDA" for short), which have 2 stacks instead of one. On any transition, 2PDAs can push and/or pop either or both stacks. (This is analogous to how multitape TMs can read/write multiple tapes on each transaction) Just as for regular PDAs, both stacks are initially empty (a) Give a formal definition of 2PDA (including of the transitions) (b) What would its configuration consist of? What would be an initial configuration? A final ion (c) Given a current configuration and a transition, how do we compute what the next configuration will be? Hint: look at the definitions of a 2-tape vs. a 1-tape TM for inspiration