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.

  • 3
    $\begingroup$ 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? $\endgroup$ – ttnick Apr 18 '19 at 12:11
  • $\begingroup$ @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 $\endgroup$ – Infinity Apr 18 '19 at 13:36

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:

enter image description here


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.