Is $L:=\{w \in \Sigma^* | \#_a{(w)} \leq \#_b{(w)} \leq 2\#_a{(w)} \}$ context-free?

Question

Given an alphabet $\Sigma:=\{a,b\}$, denote $\#_\sigma{(w)}$ the number of occurrences of a character $\sigma \in \Sigma$ in a word $w \in \Sigma^*$.

Define $L:=\{w \in \Sigma^* | \#_a{(w)} \leq \#_b{(w)} \leq 2\#_a{(w)} \}$. Is $L$ context-free?

I've tried constructing an appropriate PDA, but I'm not sure how to enforce both $\#_a{(w)} \leq \#_b{(w)}$ and $\#_b{(w)} \leq 2\#_a{(w)}$ simultaneously. Any clues?

Answer 1

I'll put this in spoiler blocks so it can be used as a sequence of hints.

Basically, the trick is to embrace non-determinism.

CFGs 1:

Have rules that produce one b and one a, and also rules that produce one b with two a's. Don't forget to leave complete freedom of ordering for the a's and b's.

CFGs 2:

So two of your rules could be T -> TaTbT and T -> TbTaTaT, though there are probably nicer solutions.

PDAs 1:

Consider the stack to be a single integer counter representing how many a's you still have to account for, so reading an 'a' can push a symbol representing "+1".

PDAs 2:

Once b's start popping those, you'll also need a way to handle negative counts...

PDAs 3:

...so reading an 'a' can ALSO pop a "-1" symbol instead.

PDAs 4:

Every b accounts for either 1 or 2 a's, so let it push one OR two "-1"s (or pop "+1"s).

PDAs 5:

Set it up so you can check for an empty stack at the end.