# Context free grammar construction

My problem with CFG is, I am to generally create ones that don't have requirements such as:

$\qquad \{a^m b^n \mid m \le n \le 2m \}$

I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting problems, along with how to solve that problem.

This is not homework, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem are the ones where I am forced to look at the solution.

• for any $a$ generate either one $b$ or two $b$'s. – Ran G. Mar 31 '13 at 7:07
• see related question cs.stackexchange.com/questions/9831/… or use the search to find others. – Ran G. Mar 31 '13 at 7:08
• If you're more comfortable with PDAs, you can always convert between the two (you get ugly grammars though). Given time, I'll write this out as a proper answer, unless someone else wants to. – Luke Mathieson Mar 31 '13 at 7:20
Just read the constraint carefully. $m\le n$ tells you that you must have at least as many b's as a's. The other part: $n\le 2m$ tells you that you cannot have more than twice as much a's.
$S\to aSb[b] \mid \epsilon$
Hint: Each $a$ corresponds to either one $b$ or two $b$s. Form a hybrid between grammars for $a^n b^n$ and $a^n b^{2n}$.