My problem with CFG is, I am to generally create ones but once they have requirements such as:
$$\{a^m b^n: 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 HW, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem with those conditions are the ones where I am forced to look at the solution. A solution that presents the thinking process behind it would help.
Thanks!
The basic idea here is that each time you generate an $a$, you should generate either one or two $b$’s to go with it. You need to do this generating in the middle, between the $a$’s on the left and the $b$’s on the right, so you want productions of the form $X\to aXb$ and $X\to aXbb$. And that’s really all that’s needed, so you can start doing that right from the beginning:
$$\begin{align*} S\to ab\mid abb\mid aSb\mid aSbb \end{align*}$$
(That’s assuming that you don’t want the empty word; if you do, just add one more alternative, $S\to\epsilon$.)
Let $m$ be the number of $a$’s at any stage of generating a word, and let $n$ be the number of $b$’s; initially $m=n=0$. Every time you apply the production $S\to aSb$ or the production $S\to ab$, you increase $m$ and $n$ by $1$. Every time you apply $S\to aSbb$ or $S\to abb$, you increase $m$ by $1$ and $n$ by $2$. Suppose that you apply $S\to ab$ or $S\to aSb$ a total of $k$ times, and the other two a total of $\ell$ times. Then you increase $m$ by $k+\ell$ and $n$ by $k+2\ell$, so you end up with $k+\ell$ $a$’s and $k+2\ell$ $b$’s. Since $k,\ell\ge 0$, we clearly have
$$k+\ell\le k+2\ell\le 2k+2\ell=2(k+\ell)\;,$$
i.e., $m\le n\le 2m$, as desired. It’s also not hard to see that we can get every value of $n$ between $m$ and $2m$: to get $n=m+d$, where $0\le d\le m$, just make sure that $\ell=d$ and $k=m-\ell=m-d$.