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.

  • 2
    $\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 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 at 13:36

Your Answer

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

Browse other questions tagged or ask your own question.