I have an odd PDA problem that I cant seem to construct. I haven't come across one like this before.

$L = \{w\in\{a,b\}^{*} : 3\#_{a}(w) \leq 5\#_{b}(w) \leq 4\#_{a}(w)\}$

Could I get some pointers on how to tackle such a problem like this so I can be more familiar with the approaches here.

  • $\begingroup$ $3n_a(w)$ means the number of $a$'s in the string? I saw a different notation, where # means the number of characters, e.g. 3*#a $\le$ 5*#b. $\endgroup$ – Evil Oct 29 '16 at 2:07
  • $\begingroup$ Yes you are correct. $\endgroup$ – James Combs Oct 29 '16 at 2:07
  • $\begingroup$ I cant seem to find a pattern that always works. Much less turn this into a grammar to construct a PDA from. In order to initially satisfy the constraints, there must either be 0 $a$'s and $b$'s or at least 3 $a$'s and 2 $b$'s. But then afterwards, I cant find a steady pattern. $\endgroup$ – James Combs Oct 29 '16 at 2:16
  • $\begingroup$ it looks like a pattern emerges. once you have 3 $a$'s and 2 $b$'s, increases both by 1 works until you have 5 $a$'s. Then you must increase the $a$'s by 2 before you increase the $b$'s by 1. Then increase both by 1 again until reaching 10 $a$'s. At which point you increase the $a$'s by 2 before increasing the $b$'s by 1 again. Im not sure if it continues this way. Not enough room to try more lol. $\endgroup$ – James Combs Oct 29 '16 at 2:25
  • $\begingroup$ I have spent too much time on this haha. Moving on $\endgroup$ – James Combs Oct 29 '16 at 2:59

It's your exercise, so you should solve it yourself... but I will give you two hints.

  1. Study the methods used in Grammar for a language with 1/3 of a's. They are helpful.

  2. Use non-determinism. Build a non-deterministic PDA. (How do you think non-determinism might help here?)

  • $\begingroup$ Thank you. Exactly what I asked for. I appreciate not giving me the answer $\endgroup$ – James Combs Oct 29 '16 at 6:17

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.