Find a Grammar G, so that L(G) = {a^i b^j c^k | k = i*j ;i, j ≥ 1}

Hello, I have difficulties solving this. I had a similar exercise, where the k was i+j, which was easier, because the solution was to just add a c for every a or b.

But I am having real trouble with this one. I am guessing Cfgs wouldnt be enough here, but idk.

Can anyone help? Thank you :)

  • $\begingroup$ Have you tried to prove whether it is not context free language? If it is not CFL you may try context sensitive. But it won’t be that interesting. $\endgroup$ Jun 5 at 5:13

1 Answer 1


The language does not satisfy the pumping lemma.

Let $p\geq 1$, and consider the word $w=a^pb^pc^{p^2}$. Note that $w\in L$ and $|w|>p$. Hence, there exists a partition $w=xuyvz$, such that $0<|uv|\leq |uyv|\leq p$, and for all $i\geq 0$ it holds that $w_i=xu^iyv^iz\in L$. Denote $n_\sigma=\#_\sigma(uv)$ for all $\sigma\in \{a,b,c\}$. Then, $0<n_a+n_b+n_c\leq p$. Note also that since $|uyv|\leq p$, it follows that either $n_a=0$ or $n_c=0$. Moreover, by pumping with $i=0$, we have $w_0=a^{p-n_a}b^{p-n_b}c^{p^2-n_c}\in L$ and so $(p-n_a)(p-n_b)=p^2-n_c$.

Cleary, $n_c$ can't be zero as otherwise $(p-n_a)(p-n_b)=p^2$ which implies $n_a=n_b=0$. Thus, $n_a=0$ and so $p(p-n_b)=p^2-n_c$.

After rearranging we have that $pn_b=n_c>0$. Hence, $n_b\neq 0$ and $n_c\geq p$ and we reached a contradiction.

  • $\begingroup$ This shows that $L(G)$ is not a CFG, which has merit, but the OP asks for a grammar $G$. $\endgroup$
    – Kai
    Aug 31 at 22:25
  • $\begingroup$ Indeed this only proves the language is not context free. Frankly, this is how I understood the question (whether it's context-free or not), but I see that perhaps the question was more general. $\endgroup$ Sep 1 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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