# PDA with 2 stacks

I urgently need a language which can be recognised by 2 PDA's but not with 1 PDA.

• Welcome back to Computer Science Stack Exchange today! Since this question has a highly upvoted answer, and our goal is to build a library of useful questions and answers, I hope you are willing to improve this question. This means rewrite the question in the form of an actual question, use more descriptive title, use correct tags, add some context, show us your research at the time, and an explanation why you think it didn't work. Thank you. Jan 25 at 14:32

(added. see also the answer obtained via our sistersite math) The languages $L_1 = \{ a^nb^nc^n \mid n\ge 1 \}$ and $L_2 = \{ a^nb^ma^nb^m \mid m,n\ge 1 \}$ are typical examples of non-context-free languages. They are easily recognized using two pushdowns. E.g., for $L_1$ store the number of $a$'s on both stacks; it can then be used to check both the number of $b$'s and $c$'s.
We can also shift the symbols from one stack to the other while doubling them. staring with $1$, and iterating we obtain powers of two. Note $\{a^{2^n} \mid n\ge 1\}$ is another example of a non-context-free language.
By my earlier remark $\{ ww \mid w\in \{a,b\}^* \}$ is another example, and makes a nice puzzle.