Consider the following generalization of pushdown automata, called Simultaneous-2Stack PDA. In this general notion, there are two stacks associated with the machine. At each step, the machine is in some state. It reads the next input symbol, the topmost symbols in the both stacks, and transitions to the next state. In addition, it changes the topmost symbols on both the stacks as follows: It either pushes symbols onto both the stacks. That is, it pushes a onto the first stack and b onto the second stack, for some a,b with being the alphabet associated with the machine. Or it pops off the topmost symbols from both the stacks. That is, if a is the topmost symbol on the first stack and b is the topmost symbol on the second stack then it pops off a and b simultaneously from both the stacks. The following moves are illegal: (a) pushing only onto one stack while keeping the other stack in- tact, (b) popping off from only one stack while keeping the other stack intact, (c) pushing a symbol onto one stack and popping off a symbol from the other stack. Show the following: Give a 6-tuple formal description of Simultaneous-2Stack PDA. Show that Simultaneous-2Stack PDA is equivalent to the PDA we taught in the class. This means that for any language L, if there exists a Simultaneous-2Stack PDA for L then there exists a PDA for L, and vice versa. Wednesday, February 3, 2021 9:37 PM FORMAL DEFINITION ( Q, E, C, D, 9., F) new w states set of Q : set of states, &: alphabet, 9: Start state, FSQ : accepting T : Stack alphabet input topmost topmost symbol (transition symbol function, 8: Q x S x power set of gr . current stale ) next State ) H stack symbol I stack (2013) (rus) Consider the following generalization of pushdown automata, called Simultaneous-2Stack PDA. In this general notion, there are two stacks associated with the machine. At each step, the machine is in some state. It reads the next input symbol, the topmost symbols in the both stacks, and transitions to the next state. In addition, it changes the topmost symbols on both the stacks as follows: It either pushes symbols onto both the stacks. That is, it pushes a onto the first stack and b onto the second stack, for some a,b with being the alphabet associated with the machine. Or it pops off the topmost symbols from both the stacks. That is, if a is the topmost symbol on the first stack and b is the topmost symbol on the second stack then it pops off a and b simultaneously from both the stacks. The following moves are illegal: (a) pushing only onto one stack while keeping the other stack in- tact, (b) popping off from only one stack while keeping the other stack intact, (c) pushing a symbol onto one stack and popping off a symbol from the other stack. Show the following: Give a 6-tuple formal description of Simultaneous-2Stack PDA. Show that Simultaneous-2Stack PDA is equivalent to the PDA we taught in the class. This means that for any language L, if there exists a Simultaneous-2Stack PDA for L then there exists a PDA for L, and vice versa. Wednesday, February 3, 2021 9:37 PM FORMAL DEFINITION ( Q, E, C, D, 9., F) new w states set of Q : set of states, &: alphabet, 9: Start state, FSQ : accepting T : Stack alphabet input topmost topmost symbol (transition symbol function, 8: Q x S x power set of gr . current stale ) next State ) H stack symbol I stack (2013) (rus)