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

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 :)

• 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. Jun 5 at 5:13

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. 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.
• This shows that $L(G)$ is not a CFG, which has merit, but the OP asks for a grammar $G$.