2
$\begingroup$

I had a question regarding a specific proof I found online that I had some concerns with, I have quoted it below.

Show that the language L = {a^i b^j c^k: i < j < k} is not a context-free language.

Solution:  If L were context free, then the pumping lemma should hold.
Let z = a^n b^{n+1} c^{n+2}.  Given this string and knowing that |z| >= n,
we want to define z as uvwxy such that |vwx| <= n, |vx| >= 1.
Because |vwx| <= n, there are five possible descriptions of uvwxy:

   1.  vwx is a^p for some p<=n, p>=1
   2.  vwx is a^p b^q for some p+q<=n, p+q>=1
   3.  vwx is b^p for some p<=n, p>=1
   4.  vwx is b^p c^q for some p+q<=n, p+q>=1
   5.  vwx is c^q for some i<=n, i>=1

   Note that because |vwx| <= n, vwx cannot contain both "a"s and "c".
   For all of these cases, u v^i w x^i y, i>=0, should be in the language.

   In case 1, if i=2 we will be adding an a to the string, making the
   number of "a"s n+1 and thus the string is not in the language.  The
   same argument holds for case 3 in which the number of "b"s will be
   equal to the number of "c"s.  A similar argument holds in case 5.
   In case 5 if i=0 then the number of "c"s will be less than or equal to
   the number of "b"s.

   In case 2, when i=2 either the number of "a"s will be greater than the
   number of "b"s or the number of "b"s will be greater than the number of
   "c"s (depending on the distribution of v and x).

   In case 4, when i=0 either the number of "b"s will be less than or equal
   to number of "a"s or the number of "c"s will be less than or equal to
   the number of "b"s (depending on the distribution of v and x).

Now my issue comes with the wording of some of these cases. Such as with case 3 where they say "The same argument holds for case 3 in which the number of "b"s will be equal to the number of "c"s." My issue is depending on the distribution of V and X is there no possibility that there would be more b's than c's in the language. I know that if there were more b's than c's in the string the pumping lemma would be contradicted. But I just wanted to confirm my intuition that based on the distribution of v and x there is a possibility that there would more b's than c's left in the string.

I also feel the same way about Case 2: where depending the distribution of v and x could there not be an equal number of a's to b's?

Thank you in advance I really appreciate the help!

$\endgroup$

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.