HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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.