4
$\begingroup$

I am trying to understand better the proof that the language $K=\{a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} is not context-free. (see It only looks like a homework problem…), and the use of Ogden's lemma as well.

I must say I have some difficulty reading @Frank Weinberg's proof as given, so I tried to write one myself. I feel it is more intuitive to follow, but is it correct ? One is easily mixed up in quantifiers with Ogden's lemma. I am not pretending my version is fundamentally different from the previous proof (assuming mine is correct). It may seem a bit longer, but I believe only because I am giving more details. My main problem with the previous proof is that I do not see why one has to define the infinite set of possible exponents.

The starting idea is the same. Given the marked-pumping length $p$. choose a word $a^i b^p c^k$ and mark all and only the $b$'s. Now, in the pumping triple $xyz$, $x$ and $z$ must contain each only one kind of symbol. Otherwise, pumping would immediately create alternation of symbols and get us out of the language, thus proving it is not CF. Condition 1 of the lemma says that at least one of them must contain $b$'s, since only $b$'s are marked. Thus $a$ or $c$ or both do not get pumped, and no more than $p$ $b$'s get pumped (condition 2 of the lemma). We want to pump exactly enough $b$'s to match either the $a$'s or the $c$'s.

Let $h$ be the product of the first $p$ positive integer. We choose $i=p+h$ and $k=p+2h$. The word $ a^{p+h} b^p c^{p+2h}$ is in $K$. We apply Ogden's lemma, marking the $b$'s as said above. Assume that for this word, it is the $a$'s that do not get pumped, and that the pumping length for $b$'s is $n$. Since $n\leq p$, $n$ divides $h$, and by applying the pump $h/n$ times we get a word of the form $a^{p+h} b^{p+h} c^k$ which is not in the language $K$. The reasonning is similar if it is the $c$'s that are not pumped. Hence the language K is not CF.

The question is : do I err, and why ? Why does Weinberg's proof require showing that there is an infinite set of exponents? Other comments are welcome too.

$\endgroup$
  • $\begingroup$ It's exactly the same proof as Frank Weinberg's, only you explicitly give $i$ and $k$ that work. By "infinite" perhaps he meant that for infinitely many $p$, the set contains at least two different integers. $\endgroup$ – Yuval Filmus Jun 13 '13 at 0:14

Your Answer

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

Browse other questions tagged or ask your own question.