[Solved]: Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?

Problem Detail: 

Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar?

I don't believe this has a context-free grammar, but please correct me if I'm wrong.

Asked By : Iancovici

Answered By : Patrick87

A two-stack PDA is equivalent in computing power to a Turing machine. Since a Turing machine can accept that language (stated without proof), a two-stack PDA can as well. The actual definition of such a machine is left as an exercise :)

Best Answer from StackOverflow

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