Automata

4. Many of you asked why we couldn't have two stacks for PDAs? Now, 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 which means that if M is at state q and reading input symbol a with the top of the two stacks being bi and b2 respectively, then this transition brings M to state P. and replaces the tops b and b2 of the two stacks to and 72 respectively. Show (describe) that any Turing machine can be simulated by a two-stack PDA 4. Many of you asked why we couldn't have two stacks for PDAs? Now, 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 which means that if M is at state q and reading input symbol a with the top of the two stacks being bi and b2 respectively, then this transition brings M to state P. and replaces the tops b and b2 of the two stacks to and 72 respectively. Show (describe) that any Turing machine can be simulated by a two-stack PDA