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
