Michael Sipser Edition 3 Exercise 3 Question 9 (Page No. 188)

Question

Let a $k-PDA$ be a pushdown automaton that has $k$ stacks. Thus a $0-PDA$ is an $NFA$ and a $1-PDA$ is a conventional $PDA$. You already know that $1-PDAs$ are more powerful (recognize a larger class of languages) than $0-PDAs$.

1. Show that $2-PDAs$ are more powerful than $1-PDAs$.
2. Show that $3-PDAs$ are not more powerful than $2-PDAs$.

(Hint: Simulate a Turing machine tape with two stacks.)