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" a
s and b
s iteratively, and each step we can do one of two things: create one a
and one b
, or create one a
and two b
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)
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}$