# Prove using pumping free lemma for context-free languages

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.

• You're not trying to disprove the pumping lemma: the pumping lemma is true. – David Richerby Apr 5 '16 at 0:34

$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