Finding the CFG of a language L

Question

I'm trying to find the CFG of language $$\mathbb{L} = {a^n b^m: n ≥ 0, 2n ≤ m ≤ 3n}$$ I'm completely stuck. I have no idea where to start. Sorry about the formatting on $\frac n m$.

Any advice would be very appreciated thank you

Answer 1

Think recursively. Grammars are recursive by their nature.

Ask yourself: if I have a valid string, how would I modify it to get a (slightly) longer string.

In this case, Suppose you have a valid string with exactly $n$ $a$s. Call that string $S$. Suppose you want a valid string $T$ which contains $S$ which has exactly $n+1$ $a$s, using a transformation:

$$T = \alpha S \beta$$

Obviously, you need to add an $a$ at the beginning, so now you know what $\alpha$ is.

Once you've gotten that, you need to ask yourself whether it is sufficient to generate all strings. So consider all valid strings with exactly $n$ $a$s, and all possible strings which result from the transformation you thought of above. Will this set contain every possible valid string with exactly $n+1$ $a$? If so you are well on your way to writing the grammar.

That explanation was much longer than the answer, which is just three production rules. But perhaps it will serve you better than just being handed the answer on a plate.