Context Free Grammar number of b's < double the number of a's

Question

I need to build a context-free grammar for $\{a^ib^j \mid j < 2i\}$

So far I have

$$\begin{align*} &S\to aSB\mid ab\mid a\\ &B\to bb\mid b\mid\varepsilon \end{align*}$$

Answer 1

Let $L$. Be the language in question. A word of the form $a^kb^\ell$ is in $L$ if and only if $k<2\ell$ or, equivalently, $\ell>\frac{k}2$. Make a small table:

$$\begin{array}{rcc} k:&0&1&2&3&4&5\\ \ell\ge:&1&1&2&2&3&3\\ \ell>:&0&0&1&1&2&2 \end{array}\tag{1}$$

Notice that there will always be at least one $b$, and as long as we have enough $b$s, we can have as many as we want. This suggests that we could start with a production $S\to XB$, where $B$ will ultimately generate a string of one or more $b$s, and $X$ will generate the $a$s and $r$ $b$s, where $r$ is chosen so that $r+1$ meets the minimum requirement $r+1>\frac{k}2$. That is, we want $X$ to generate strings of the form $a^kb^r$, where $r$ is the number in the bottom row of table $(1)$ corresponding to $k$ in the top row. (You can check that in fact $r=\left\lfloor\frac{k}2\right\rfloor$.)

It’s easy to design productions so that $B$ generates all strings of one or more $b$s: $B\to bB\mid b$. It’s a little trickier to get $X$ to generate all strings of the form $a^kb^{\lfloor k/2\rfloor}$, but still not too bad. After applying $S\to XB$, you’ll have the string $XB$, and you know that the $B$ will eventually produce $b^{n}$ for some $n\ge 1$, so you’ll have $Xb^n$. The $X$ will produce $k$ $a$s and $r=\lfloor k/2\rfloor$ $b$s for some $k$. At the moment $k=r=0$: $X$ hasn’t produced anything. If we simply make $X$ go away, we end up with $b^n$ for some $n+1$, which is fine: that’s in $L$. Thus, we want $X\to\epsilon$ to be a possibility. We could also have $k=1$ without increasing $r$: that would give us $ab^n$ for some $n\ge 1$, and that too is in $L$. Thus, $X\to a$ should also be a possibility. Finally, we need to allow for $k\ge 2$.

Notice that when we add a second $a$, $r$ goes up to $1$, and we have to add another $b$ as well. We can do this by having a production $X\to aY$ to add an $a$ and keep going. At this point we have $aYb^n$ for some $n\ge 1$, and we want the $Y$ to generate at least one more $a$ and a $b$ to go with it. We also want to be able to keep going, adding more $a$s if we wish, so there should be some non-terminal on the righthand side: $Y\to aZb$ for some $Z$. Do we actually need a new non-terminal here, or can $Z$ be one that we already have?

After we apply this production, we’ll have the string $a^2Zbb^n$, with $k=2$ and $r=1$. At this point we could stop, we could add an $a$ and stop, or we could add an $a$ and keep going. Those are exactly the same choices that we had when we’d reached the stage $Xb^n$, and we designed $X$ to handle those choices, so we can take $Z$ to be $X$. If we do that, we end up with the following productions:

$$\begin{align*} &S\to XB\\ &B\to bB\mid b\\ &X\to aY\mid a\mid\epsilon\\ &Y\to aXb \end{align*}$$