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

Question

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

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.