Can I solve pumping lemma for context free language proofs using examples?

Question

Say I need to prove that

$L=${$a^n b^n c^n; n\geq 1$} is not context free language

I take n=3. w=aaabbbccc

Here |w|=9.

we know by pumping lemma-:

|vxy| $\leq$n so vxy=abb

|vy| $\geq$1 so vy=ab

Hence I suppose-: u=aa v=a x=b y=b z=bccc

So

$u v^i x y^i z$ =aaaabbbbccc

Hence it is not in L so L is not regular.

But this looks funny to me to be approved in exam. Will it be approved in exam in your opinion? I know it is broad question but there must be CS teachers in cs.stackexchange to know about this? The other proof of this is too hard for me to understand. So I have resorted to this.

Answer 1

That's an incorrect proof. There are two reasons.

You say that you need to prove that $L$ is a context-free language. The pumping lemma cannot help you with that, since it can only be used to prove that $L$ is not regular (which doesn't imply that $L$ is context free) or that $L$ is not context-free (in its variant for context-free languages).

Assuming instead that you wanted to prove that $L$ is not a regular language, it is not correct to just pick "an example" word.

The pumping lemma statement is as follows:

Pumping lemma: if $L$ is regular, then there exists some positive integer $p$, such that for every word $w$ with $|w|\ge p$, there exists a way to write $w$ as $xyz$ with $|xy| \le p$ and $y \ge 1$, such that for every integer $i \ge 0$, $xy^iz \in L$.

If you want to show that $L$ is not regular, then you need to prove that the pumping lemma does not hold for $L$. In other words you need to show that the following holds:

Negation of Pumping Lemma: for all positive integers $p$, there exists a word $w$ with $|w|\ge p$ such that, for every possible choice of $x,y,z$ with $w=xyz$, $|xy| \le p$, and $|y| \ge 1$, there exists an integer $i \ge 0$, such that $xy^iz \not\in L$.

This means that you cannot choose a fixed length of $|w|$. Moreover, you cannot choose the decomposition of $w$ into $x$, $y$, and $z$, but you need to consider all possible decompositions (that satisfy the constraints of the statement above).

Here is a proof that your specific $L$ is not regular by showing that "Negation of Pumping Lemma" holds.

Given any value of $p$ (recall that our proof must hold for all $p > 0$), we choose $w=a^p b^p c^p$ and we notice that $|w| = 3p \ge p$. We are allowed choose $w$ since we only need to show that a suitable word $w$ exists.

We now consider all possible ways of writing $w$ as $xyz$ with $|xy|\le p$ and $|y| \ge 1$. Notice that $xy$ must contains only $a$s, therefore $x$ must be of the form $a^j$ for some $j \ge 0$, $y$ must be of the form $a^h$ for some $h \ge 1$, $j+h \le p$, and $z$ is of the form $a^{p-j-h}b^p c^p$.

Next, we pick a value for $i$ (a single value suffices since we only need to show that a suitable value exists). In particular we choose $i=0$.

We need to verify that $x y^i z \not\in L$. This is true since: $$ x y^i z = a^j (a^h)^i a^{p-j-h}b^p c^p = a^{p-h}b^p c^p, $$ and $h \ge 1$.

This shows that "Negation of Pumping Lemma" holds for $L$, i.e., that the Pumping Lemma fails for $L$. As a consequence $L$ cannot be regular. This concludes the proof.

Answer 2

There are very many flaws in this proof attempt, and I would not give marks for this.

First of all: $L$ is NOT context-free and the pumping lemma for context-free languages can only be used to prove that a language is NOT context-free. Similar to the better-known pumping lemma for regular languages, there are non-context free languages that have the pumping properties required by the lemma.

Second: the pumping properties rely on the assumption that there exists a finite pumping length $p$, and that only strings containing $p$ or more symbols are subject to the requirements of the lemma. Therefore, you can't use the string $aaabbbccc$, because it's possible $p > 9$ for all possible pumping lengths $p$ of $L$ in which case we wouldn't expect the conditions to hold anyway. You can use any $s \in L$ with $|s| \geq p$, for instance $a^pb^pc^p$.

Third: after you have fixed the string for observation, eg. $s = a^pb^pc^p$ as above you must present the $uvxyz$ division under the conditions given is impossible to satisfy. You have to show that every choice of $uvxyz$ fails at least one of the lemma's conditions. The choice of $s$ here matters a lot: as the "center part" of the string is bounded in length – more formally, $|vxy| \leq p$, you know that $v$ and $y$ contain no $a$ symbols, no $c$ symbols, or neither symbol, which gets you the expected result of $L$ being non-context free.

Try again with these notes in mind, and I think you will have an easier time.