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?
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"
a
s andb
s iteratively, and each step we can do one of two things: create onea
and oneb
, or create onea
and twob
s.(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)