Context free grammar for $=\left\{^n ^m\mid0<≤≤4+3 \right\}$

Question

I tried to start writing the grammar but was only successful when $m = n$:

$$S \to ab \, |\, aSb$$

As for the rest, I can not find out about the legality I would be happy if you could help me.

Answer 1

If you want just a context-free grammar with $0<m\leq n$ you could do the following:

$$ S \to ab \mid aSb \mid aS $$

However, that would allow $n>4m+3$ as well. Therefore we need to make sure that this can't happen:

\begin{align} S_1 &\to aS_2b \\ S_2 &\to aTb \mid U \mid \varepsilon\\ T &\to S_2 \mid aS_2 \mid aaS_2 \mid aaaS_2 \\ U &\to a \mid aa \mid aaa \end{align}

Above grammar works. Why? $T$ makes sure that for every $b$ we can get at least one and at most four $a$. To get the additional $+3$, when finishing everything, we allow a maximum of three additional $a$ using $U$. Therefore we make sure that $m \leq n \leq 4m+3$.

As $m>0$ we need to split the start between $S_1$ and $S_2$ to make sure that at least one $a$ and $b$ are visible.