Is this enough to prove that the language L is not context-free? (Pumping lemma for CFL's)

970 Views Asked by At

The language $L = a^nb^nc^n | n>=1$

We assume that the language $L$ is context-free. Then it must satisfy these conditions:

We can break any string $Z$, where $|Z| >= p $ into 5 substrings: $uvwxy$

So I choose the string:

$Z = a^pb^pc^p$

Now I need to show that the string $uvwxy$ satisfies these conditions:

$|vx| >= 1 $, $|vwx| <= p $, and $uv^iwx^iy$ is in $L$, for all $i>=0$

For all the cases that satisfies the first 2 conditions, we have:

Case 1: $vx$ is composed of a mix of $a$'s and $b$'s (in that order). If we choose $i=0$, then the number of $c$'s will be greater than the number of $a$'s or $b$'s, thus not being part of the language

Case 2: $vx$ is composed of a mix of $b$'s and $c$'s (in that order). If we choose $i=0$, then the number of $a$'s will be greater than the number of $b$'s or $c$'s, thus not being part of the language

Case 3: $vx$ is composed of just $a$'s, $b$'s or $c$'s. With $i = 0$, the letter chosen becomes less than the number of both unchosen letters, which is not part of the language.

Since $Z$ cannot satisfy these conditions, $L$ is not a CFL.

1

There are 1 best solutions below

3
On BEST ANSWER

It looks good to me.

In general, for pumping lemma proofs by contradiction, you need to show that for all ($\forall$) pumping lengths there exists ($\exists$) a string $s$ (with $|s|\ge p$) that cannot be pumped.

In your case, you chose a generic pumping length $p$. And you found a counter-example string $s$ that absolutely cannot be pumped (i.e. you showed that all possible cases cannot be pumped). Therefore, you've showed that for any arbitrary pumping length $p$, you can construct a string $s$ that cannot be pumped by the Pumping Lemma for CFL's. Thus, you've contradicted that $L$ is a CFL.