in Theory of Computation
198 views
0 votes
0 votes

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.)

in Theory of Computation
198 views

Please log in or register to answer this question.

Related questions