PDA - Sum of Two Characters = Sum of Two Other Characters For one problem I have to solve, I'm given a Language:

L = {a^r b^s c^t d^u | r+s = t+u}


And from it told to construct a PDA that accepts it. I can construct a PDA for 

L1 = {a^r b^s | r,s &gt;= 0}


And for

L2 = {c^t d^u | t,u &gt;= 0}


As they are, essentially, the same language. However, I'm confused as to how I can make sure that the sum of characters in L1 equal those in L2
You can probably build a PDA for the language $\{p^nq^n\mid n \ge 0\}$. If so, you're almost there. Just treat the a's and b's as if they were all p's and the c's and d's as if they were q's, like this (with details elided): 


Count the a's and b's by pushing a marker on the stack for each one (making sure that all the a's precede any b).
Match them up with the c's and d's: for each one seen, pop a marker off the stack (again, making sure that the input is correctly formed).
If the stack is empty after having read all the input, accept.