Designing CFG that accepts a^n b^m (n<m<2n)

Designing CFG for the following language $\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n\le m \le 2n \}$ is easy.

$S \to aSb \mid aSbb \mid \lambda$

Then how about this? Language $\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n<m<2n \}$.

It is somewhat difficult for me. I have no idea how to exclude $n=m$ or $m=2n$.

Could you give me some hints?

Try this to remove the two cases the first time :

$$S\to aAb$$ $$A\to aCbb$$ $$C\to aCb|aCbb|\lambda$$

If you go to $A$ you cannot have $a^nb^{2n}$ and while going from $A$ to $aCbb$ you are removing the possiblity to get $a^nb^n$.

• I've checked it and I could not generate any contradictory string. It seems to be correct. Thank you for your answer. – newbie16 Jun 6 '17 at 9:21

The only way in which your original grammar produces a string of the form $a^nb^n$ is if the production $S\to aSbb$ is never used. Similarly, the only way in which it produces $a^nb^{2n}$ is if $S \to aSb$ is never used. We thus want to force both of them to be used. Since all these productions "commute" (it doesn't matter in which order you apply them), we might as well assume that the first thing you do is apply these two productions, and the rest is arbitrary. The corresponding grammar is

\begin{align*} &S \to aaTbbb \\ &T \to aTb \mid aTbb \mid \lambda \end{align*}

If instead we apply these two productions at the end, we get an even more succinct grammar: $$S \to aSb \mid aSbb \mid aabbb$$

Alternatively, notice that $n < m < 2n$ is equivalent to $n-2 \leq m-3 \leq 2(n-2)$. This is since $n < m$ iff $n-2 \leq m-3$, and similarly $m < 2n$ iff $m-3 \leq 2n-4$. We can therefore write the language as \begin{align*} L &= \{ a^nb^m \mid n-2 \leq m-3 \leq 2(n-2) \} \\ &= \{ a^{n+2} b^{m+3} \mid n \leq m \leq 2m \}. \end{align*} The grammars above implement the latter form.

• thank you for your detailed explanation. I've learned a lot. thanks. – newbie16 Jun 7 '17 at 4:56