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.

  • 2
    $\begingroup$ for any $a$ generate either one $b$ or two $b$'s. $\endgroup$
    – Ran G.
    Mar 31, 2013 at 7:07
  • 1
    $\begingroup$ see related question cs.stackexchange.com/questions/9831/… or use the search to find others. $\endgroup$
    – Ran G.
    Mar 31, 2013 at 7:08
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 31, 2013 at 7:20
  • $\begingroup$ read this answer wil help you if you want I can answer here too $\endgroup$ Mar 31, 2013 at 20:07
  • $\begingroup$ I don't understand the problem ... now we know what requirements are not on your CFG, but what are the requirements? $\endgroup$ Mar 31, 2013 at 20:15

2 Answers 2


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.

Here is an EBNF description that yon can convert to BNF.

$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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.