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.

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.