[Math] Context free grammar for the language

context-free-grammarformal-languages

I had to make a context free grammar for the following language:
$$
\{a^m b^n \mid 1 \le m \le n \le 2m\}
$$

What I thought is:
\begin{align*}
S &\to aXbb \\
X &\to a|aab|abb|ab|E
\end{align*}

Is this correct way of writing a CFG?

Best Answer

It's interesting to see so many different ideas. My own hint is that we can produce words by "creating" as and bs iteratively, and each step we can do one of two things: create one a and one b, or create one a and two bs.

(be aware that each answer so far is leading towards a different presentation of the grammar: you can't combine the hints directly, and should probably only think about one at a time)

Related Question