I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG.

I have thought about solving this for a long time but but this still hasn't gotten me very far

Any help would be appreciated Thanks


$$ \begin{align*} S \to & AbBC \mid AbBCc \mid AbBCcc \; \mid \\ & aAbBC \mid aAbBCc \mid aAbbBCcc \; \mid \\ & aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\ B \to & bB \mid \epsilon \\ A \to & aaaAb \mid \epsilon \\ C \to & bCccc \mid \epsilon \end{align*} $$

The intuition is as follows:

The nonterminal $B$ encodes the fact that we can have any number (possibly 0) of extra occurrences of $b$s in addition to those strictly needed to satisfy $i+k < 3j$.

For every $3$ occurences of a $a$s or $c$s we have to "pay" by adding one $b$ to our word. The nonterminal $A$ (resp. $C$) represents a triplet of $a$s (resp. $c$s) along with the occurrence of $b$ that is used to "pay" for the triplet.

Clearly, our word might have a number of $a$s (resp. $c$s) that is not a multiple of $3$, however there are only $9$ possible cases for the combinations of the remainders $i \bmod 3$ and $k \bmod 3$. These cases are explicitly handled in productions from the axiom $S$, in which we make sure to add at least $\left\lceil 1+\frac{(i \bmod 3) + (k \bmod 3)}{3} \right\rceil$ additional "b"s to "pay" for the $(i \bmod 3) + (k \bmod 3)$ extra characters (the $+1$ ensures that the "greater than" in the inequality $i+k < 3j$ is satisfied).

| cite | improve this answer | |

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.