Language to CFG

Question

I have the following exercise. I have to create a CFG from the following language:

M = {a^m b^n| 2m > n > m}

Currently I have:

S -> aaSbbb

A -> aaA

B -> bbbB 

Im not sure if this is correct. Also how do I apply limit so that 2m > n still holds instead of just n > m where n can just be any number as long as it is bigger than m

Answer 1

The $A$ and $B$ rules would make it possible to increase either $m$ or $n$ without increasing the other. For example, if you had a string with an $A$ in it, then rule $A \to aaA$ would let you make as many '$a$'s as you wanted without regard to how many '$b$'s get produced by any other applications of the rules.

On the other hand I don't see how either of the rules for $A$ or $B$ could ever get invoked. (You start with just $S$, right?)

In order to prevent runaway production of either '$a$'s or '$b$'s, there is a very limited choice of where in the string you can allow a rule to be invoked that produces either '$a$'s or '$b$'s.

Below is a graph that shows how many '$a$'s a string has (the number on the bottom row) and how many '$b$'s it has (the number in the left column). For each combination of '$a$'s and '$b$'s, there is a $*$ if the string is a member of your language. I have only taken this up to $m=5$ but you can extend the table to the right and upward.

\begin{matrix} 9 & & & &* \\ 8 & & & &* \\ 7 & & &*&*\\ 6 & & &*&*\\ 5 & &*&*\\ 4 & &*\\ 3 &*\\ &2&3&4&5 \end{matrix}

You have identified a rule $S \to aaSbbb$ that produces the shortest possible string in the language-- or at least it almost does that, because there's still an $S$ in that string, and you have no way to eliminate $S$. All you can do is keep on applying that rule and producing more '$a$'s and '$b$'s with a new $S$ in the middle.

At some point you need a rule with $S$ on the left and without $S$ on the right. Also, you need at least one rule that has only '$a$'s and '$b$'s on the right (possibly the empty string). Otherwise you'll never reach a point where you have a string with only '$a$'s and '$b$'s in it and can stop applying rules. Of course, these could be the same rule.

So you want to be able to get to the count $m=2,n=3$ and stop there. You also want to be able to get to any of the other strings represented in the graph (and stop there).

You have a couple of choices about how to do this. You can make sure you produce at least two '$a$'s and three '$b$'s, and then have additional rules that let you insert additional '$a$'s and '$b$'s (while staying inside the "legal" area of the graph) or stopping. Or you could produce all the "additional" '$a$'s and '$b$'s first and then insert $aabbb$ in the middle. Or you could allow some combination of the two procedures, but it seems to me a simpler set of rules is better.

Answer 2

You can create a production for the upper bound by

$U\rightarrow ab^2 | aUb^2$

Then your valid strings are

$S \rightarrow aUb | aSb$

To see that this generates the grammar note that if $S = a^mb^{m+k}$ where $0\lt k\lt m$ then $S = a^{m-k}a^kb^{2k}b^{m-k}$.