Prove using pumping free lemma for context-free languages

Question

One of the exercises I tried to make I failed miserably.

The question was as follows:

Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ being the number of a's in the word, same for b's and c's)

For answers I first looked at common words not accepted by context free languages like $a^pb^pc^p$ with $p$ being the pumping length.

However I could not make a proof. Finally I got tired and with made the following construction. I assumed the length dynamic part of the ab's substring would only be one. (then it doesn't matter that much whether it is an 'a' or 'b', I chose the latter). And constructed my word like this:

$\theta b c^{n_a(\theta)} c^{n_a(\theta)\cdot n_b(\theta)}$, with $\theta$ being some random string in $\{a,b\}^*$with 'b' being the dynamic substring v and $c^{n_a(\theta)}$ being the dynamic substring y.

With this construction $uv^0xy^0z = \theta c^{n_a(\theta)\cdot n_b(\theta)}$, which is in the language, and $uv^ixy^iz = \theta b^i c^{i\cdot n_a(\theta)} c^{n_a(\theta)\cdot n_b(\theta)}$ is also in the language.

In other words, any string where I seperate the ab's from the c's I can prove that even by taking a v of size 1, I will always find u,v,x,y,z substrings that match.

At this point I don't really know how to construct a word any more to disprove the pumping lemma. It's very obvious that there has to be one, but not so obvious what I should look at.

Any help would be greatly appreciated.

Answer 1

i figured it out

$w = (ac^pb)^p $ cannot be split.

in the case that vxy consists of only a's and b's $uv^0xy^0z $ would have less a's and b's but not less c's.

in the case that vxy consists of only c's $uv^0xy^0z $ would have less c's but not less a's and b's.

in the case of a combination it might have an a or a b or both. if it has an a, the number of c's needs to increase by p, but $|vy| \le p$ and we'd need p + 1 terminals. for b the same holds, and for an a and a b it would need even more c's.

so we cannot split this word into 5 substrings u,v,x,y,z such that $uv^ixy^iz$ is in L

Answer 2

Assume $L$ is context free, thus it satisfies the pumping lemma. Call the constant of the lemma $p$. Pick the string $\sigma = a^p b^p c^{p^2} \in L$, and $\lvert \sigma \rvert = p^2 + p \ge p$. By the pumping lemma, you can write $\sigma = u v w x y$ so that $\lvert v w x \rvert \le p$, $x, y$ not both $\epsilon$, such that for all $k \ge 0$ it is $u v^k w x^k y \in L$. Now consider all possible ways to break up $\sigma$ complying with the conditions. By the length condition, $v w x$ is at most two types of symbols. But then repeating $v$ and $x$ unbalances at least the number of times the third symbol appears

We are forced to conclude that no division works, the language doesn't comply with the pumping lemma. It can't be context free.