Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}

Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$

I'm trying to write a grammar for this language? I don't know how to do this. I tried this:
$S \rightarrow aaAb \mid aA \\ A \rightarrow aA \mid a$

• You could simplify the task by splitting the language: $L = \{ a^i b^j \mid i < 2j \} \cup \{ a^i b^j \mid i > 2j \}$ Feb 15 '13 at 11:55
• The reasoning being that CFG's are closed under union. Feb 15 '13 at 11:59
• Basically the question is already answered here: Context Free Grammar for language Feb 15 '13 at 19:15

Consider the two languages:
$L_1 = \{a^ib^j \mid i, j \ge 0 \text{ and } i > 2j\}$
$L_2 = \{a^ib^j \mid i, j \ge 0 \text{ and } i < 2j\}$

Convince yourself that $L = L_1 \cup L_2$.

In $L_1$, the number of $a$'s are more than double of $b$'s, so there has to be atleast one $a$ (when there are no $b$'s). Also, for every addition of $b$, atleast 2 $a$'s must be added. You can generate $L_1$ as:

$S_1 \rightarrow aA \\ A \rightarrow aaAb \mid aA \mid \varepsilon$

$L_2$ is a little more tricky. The number of $a$'s are less than double the number of $b$'s, so there can be $0$ $a$'s, but non-zero $b$'s. Consider the "base case" of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$'s by at most $2$. So we can add $0$, $1$, or $2$ $a$'s for every addition of $b$. We'll let the second rule handle this. So, the CFG for $L_2$ becomes:

$S_2 \rightarrow Bb \mid aBb \\ B \rightarrow Bb \mid aBb \mid aaBb \mid \varepsilon$

Note that CFG's are closed under union, that is, the union of two CFG's is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L_1$, or of $L_2$:

$S \rightarrow S_1 \mid S_2$

The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.

Start with a grammar for $\{a^i b^{2 i} : i \ge 0\}$: $$S \rightarrow a S bb \mid \epsilon$$ Now hack it so that there are more $a$ than $bb$: \begin{align*} S &\rightarrow a S bb \mid A \\ A &\rightarrow a A \mid a \end{align*} The modificaton to force more $b$ is similar, and left to you. It adds a nonterminal and three productions.

• This will not generate strings of all $a$'s or all $b$'s, which are a part of $L$. Feb 15 '13 at 13:49
• If I change the question to i,j≥1 and i≠j and i<2j so how can i think of solution? Feb 15 '13 at 17:45
• @Paresh, the part of extra $b$s is left to complete. And all $a$s is $S \Rightarrow A \Rightarrow^* a^k$. Feb 15 '13 at 18:06
• Aah ... I don't know how I missed that. Sorry! Feb 15 '13 at 18:11
• @Vonbrand the problem that i dont know i to do the extra bso that it will not be more then the a. Feb 15 '13 at 20:13