How to split a context-free language into three sub-languages?

Question

I try to split the language $$ L = \{a^ib^j \mid i \neq 2j, i \neq 3j\} $$ into three languages \begin{align} L_1 &= \{a^ib^j \mid i < 2j\} \\ L_2 &= \{a^ib^j \mid 2j < i < 3j\} \\ L_3 &= \{a^ib^j \mid i > 3j\} \end{align} and then use one more production $S = S_1|S_2|S_3$, but I have no idea how to find the CFG for $L_2$.

Answer 1

The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$: $$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$ We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, and the other one to be the last: $$ \begin{align*} &S \to a^2 T b \\ & T \to a^2 T b \mid a^3 T b \mid a^3 b \end{align*} $$ Alternatively, let us notice that the condition $2j < i < 3j$ can be written as $2j+1 \leq i \leq 3j-1$, and also as $2(j-2) \leq i-5 \leq 3(j-2)$. This implies the even simpler grammar $$ S \to a^2Sb \mid a^3Sb \mid a^5 b^2 $$