PDA with an unusual double inequality

Question

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.

$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. — Evil, Commented Oct 29, 2016 at 2:07
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. — James Combs, Commented Oct 29, 2016 at 2:16
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. — James Combs, Commented Oct 29, 2016 at 2:25

Community · Accepted Answer · 2017-04-13 12:48:34Z

1

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

Study the methods used in Grammar for a language with 1/3 of a's. They are helpful.
Use non-determinism. Build a non-deterministic PDA. (How do you think non-determinism might help here?)

CommunityBot

1

answered Oct 29, 2016 at 4:31

D.W.♦

166k21 gold badges230 silver badges490 bronze badges

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

Add a comment |

1 Answer 1