Problem 4. (10 points) A 2-stack PDA is a PDA with two stacks; its input tape is 1-way read-only. In one step push and pop, operations can be performed on both stacks.

1. a) Describe, at a high-level, a 2-stack PDA to recognize the language {:0}.
2. b) Can a 2-stack PDA recognize the language {:0}.
3. c) Can a 2-stack PDA recognize every Turing-recognizable language? Explain your reasoning.

Problem 4. (10 points) A 2-stack PDA is a PDA with two stacks; its input tape is 1-way read only. In one step push and pop operations can be performed on both stacks. a) Describe, at a high-level, a 2-stack PDA to recognize the language {a bc: n >0}. b) Can a 2-stack PDA recognize the language {a" bc d:n > 0}. c) Can a 2-stack PDA recognize every Turing-recognizable language? Explain your reasoning