A two-stack pushdown automaton (2-stack PDA) is exactly like a pushdown automaton except that it has two stacks from which we can push and pop at each step. More formally, a 2-stack PDA consists of a 6-tuple (Q, , , , q0, F) where the transition function is dened as

: Q P(Q ) If (q0,b0 1,b0 2) (q,a,b1,b2),

it means that the 2-stack PDA at state q can read the input symbol a, pop b1 from the rst stack, pop b2 from the second stack, push b0 1 onto the rst stack, push b0 2 onto the second stack, and go to state q0. Acceptance for a 2-stack PDA is just as in a regular PDA. Show that a language is Turing-recognizable if and only if it can be recognized by a 2-stack PDA.