CFG for L = {a^mb^nc^k: k = m×n}

Question

Can we write CFG for this language? I searched multiple websites but I couldn't find any answers.

Answer 1

We can prove this is not context-free using the pumping lemma for context-free languages, as follows.

Assume the language were context-free. Then we'd be able to write any string w in the language as w = uvxyz where |vxy| <= p, |vy| > 0 and for all integers k >= 0, u(v^k)x(y^k)z is also a string in the language.

Consider the string a^(2p) b^(3p) c^(6p^2). This is a string in our language since 2p x 3p = 6p^2. Now, consider the five cases for the placement of the substring vxy:

1. vxy consists only of a's. Pumping down by at least one will reduce the product by at least 3p, breaking the equality.
2. vxy consists of a's and b's only. Pumping down will reduce the product by at least 2p, breaking the equality.
3. vxy consists of b's only. Pumping down will reduce the product by at least 2p, breaking the equality.
4. vxy consists of b's and c's. If we pump down, we must remove at least one b but no more than p c's; because we'd need to remove at least 2p c's to keep the equality true, this breaks it.
5. vxy consists only of c's. pumping down reduces the product without reducing the multiplicands, which can't maintain the equality.

In all five possible cases we see the equality cannot be maintained while pumping down (choosing k = 0) and so our string cannot be pumped down. But then the language cannot be context-free.