3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.