1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. Given the type of question it is (Asking for confirmation if something is right), can I mark an answer to a question like this as answered? Or should all the answers be voted upon. (new to the site) $\endgroup$ – Andrew Kor May 3 at 0:29
  • $\begingroup$ @AndrewKor If you think it sufficiently explained why your proof is correct, then you can mark it as correct. If you are unsure or need more details feel free to ask or wait for more votes. See this meta post for more info on proof-verification questions. $\endgroup$ – Dando18 May 3 at 0:53
  • $\begingroup$ Thanks. Would you mind taking a look at this question? Pumping lemma to prove L is not regular $\endgroup$ – Andrew Kor May 3 at 1:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.