patternMinor
Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?
Viewed 0 times
canstackfreeacceptlanguagepdatwocontextwhichnot
Problem
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.
I don't believe this has a context-free grammar, but please correct me if I'm wrong.
Solution
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 :)
Context
StackExchange Computer Science Q#10892, answer score: 6
Revisions (0)
No revisions yet.