# aⁿbⁿcⁿdⁿ using 2-stack PDA

I need to construct a PDA using 2 stacks for accepting the language $$L = \{a^nb^nc^nd^n |$$ $$n \geq 0\}$$.

Pushing $$a$$'s to first stack and $$b$$'s to second and poping them for corresponding $$c$$'s and $$d$$'s respectively won't work because that would mean number of $$a$$'s $$=$$number of $$c$$'s and number of $$b$$'s$$=$$ number of $$d$$'s. I can't come up with an accurate solution.

• Hint: Push $a$s on first stack for each $a$, pop $a$ from first stack for each $b$ and simultaneously push $a$s to second stack. Can you proceed from here? – ttnick Apr 18 '19 at 12:11
• @ttnick hey! thank you! Yes, I can proceed from here. I will pop second stack a's for every c and add c's to the first stack simultaneously and then pop them all for d's. :D – Infinity Apr 18 '19 at 13:36

2 stack PDA to recognize the language {an bn cn dn n>=0} for this we should follow the given steps:

Use the first stack for checking an bn, this can be done by pushing a whenever you see an a and then popping a when you see a b.

Use the second stack for checking bn cn this can be done by pushing b whenever you see a b and then popping b when you see a c.

Use the first stack for checking cn dn this can be done by pushing c whenever you see a c and then popping c when you see a d.

Accept if both stacks are empty at the end of this process, otherwise do not accept it.

Let ^ and z be the stack symbol of stack 1 and 2 respectively, then the transition diagram of the above PDA will be as follows:

A 2-stack nondeterministic PDA is easily shown to be equivalent to a nondeterministic Turing machine—just use the two stacks as the left and right halves of the tape. So you could just write a Turing machine that accepts the language and then convert that to a 2-stack PDA.

Not as elegant as ttnick's/Devharsh Trivedi's solution, perhaps, but it avoids having to be clever with stack management.