PDA with 2 stacks

Problem Detail: 

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

Asked By : nurgasemetey

Answered By : Hendrik Jan

A machine using two pushdowns accepts the recursively enumerable languages. So there is a lot to choose from. Look for your favourite non-context-free language, and build a two-stack machine for it!

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11925