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.
Check out this link: https://stackoverflow.com/questions/40317006/pushdown-automaton-pda-for-l-anbncnn-1#= or check the answer below.
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.
