I have the language L = {a^ib^jc^k : 0 \leq i \leq j \leq k} and I want to prove that is not context-free.

So I started like this:
p\in \mathbb{N}_{0} is variable.
Choose w = a^pb^pc^p

Case 1:
vxy has no c. Choose i = 2
uv^ixy^iz has more a than c or more b than c.
\Rightarrow uv^ixy^iz\notin L

Case 2:
vxy has no a.

At case 2 I don't know how to continue, I'm confused since I seem to be not able to prove that there is a case where vxy has no a and the word's b-count or c-count is smaller than the amount of a's.

  • $\begingroup$ The pumping lemma also includes the case $i=0$ (where the $i$ is from the Lemma, not the $i$ from the definition of $L$). $\endgroup$ – Hendrik Jan May 14 '16 at 17:11
  • $\begingroup$ What are you trying to say? You mean I shouldn't be shadowing those variables? $\endgroup$ – Leo Pflug May 14 '16 at 17:13
  • $\begingroup$ In Case 2 take $i=0$ in the pumping. That will delete $b$'s and or $c$'s while the $a$'s stay constant. What I added is that there is another $i$ in the definition of $L$. That can be confusing, but with some care you are OK. $\endgroup$ – Hendrik Jan May 14 '16 at 18:29
  • $\begingroup$ Ah thanks. so those 2 cases are enough, right? $\endgroup$ – Leo Pflug May 14 '16 at 18:54
  • $\begingroup$ Yes, but you have to argue that, using the length condition on $vxy$. $\endgroup$ – Hendrik Jan May 14 '16 at 23:08

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.