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?
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?
CFG should be $$S\rightarrow aSb|aSbb|ab|abb$$
where $S$ is the start symbol.
So for example if you have to produce the word $a^mb^n$ then as we know $m\leq n\leq 2m$ then you will use $2n-m$ times this production ($S \rightarrow aSb$) and $m-n$ times this production ($S \rightarrow aSbb$).
hence you will get $(2n-m)+(m-n) \times a$ and $(2n-m)+2(m-n)\times b$ which is desired.
Again if $m\leq n\leq km$ then CFG would be $$S\rightarrow aSb|aSbb|.....|aS\underbrace{bb....b}_{\text{k times}}|ab|abb|......|a\underbrace{bb....b}_{\text{k times}}$$ and here also logic is same.
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)
It's not correct. Consider the word $a^4b^5$. This word belongs to the language because $m=4$, $n=5$ and $1 \le 4 \le 5 \le 2 \times 4$. However, your grammer cannot produce it, as it can produce three "$a$"s at most.
Here is a hint: Make $S$ produce one $a$, one $b$ and one $B$ recursively. Make $B$ produce one $b$ at most. This ensures that $1 \le m \le n$, and $n \le 2m$.
Hint: $$a^m b^n = a^{2m-n}a^{n-m}(bb)^{n-m}b^{2m-n}$$