# 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 >= 0}


And for

L2 = {c^t d^u | t,u >= 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

• Both $L_1$ and $L_2$ are regular; you have to get at the non-regular essence.
– Raphael
Nov 14 '14 at 11:09

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):
• So, for every a I push, I can push something like a #, the same with b. So the stack would look something like a#a#b#b#b#? Nov 14 '14 at 16:31
• I think I see what you mean. So I just push a specific marker for c, and a different one for d. Then, for each c I read, pop one of its stack markers, and then for each d I read, pop one of its stack markers? Nov 14 '14 at 17:56
• What if I want r + t = s + u? Nov 17 '14 at 3:55