0
$\begingroup$

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

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

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):

  1. 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).
  2. 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).
  3. If the stack is empty after having read all the input, accept.
$\endgroup$
6
  • $\begingroup$ 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#? $\endgroup$
    – Delfino
    Nov 14 '14 at 16:31
  • $\begingroup$ @Delfini. You don't need the a's or b's on the stack, just the counting markers. $\endgroup$ Nov 14 '14 at 17:48
  • $\begingroup$ 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? $\endgroup$
    – Delfino
    Nov 14 '14 at 17:56
  • $\begingroup$ @Delfini. Not quite. You want to see that the number of a's and b's together is equal to the number of c's and d's together, so count the number of a's and b's by pushing a marker (the same one) for every a seen and every b seen. Then, every time you see a c or a d, pop one of the markers off. If after having read all the input, the stack is empty, that will mean that the number of a's and b's in total is equal to the number of c's and d's in total. $\endgroup$ Nov 14 '14 at 19:28
  • $\begingroup$ What if I want r + t = s + u? $\endgroup$
    – Delfino
    Nov 17 '14 at 3:55

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.