3
$\begingroup$

I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a CFL.

Now, in the book they do it in a way that I understand but I think it can be simplified, so here goes:

Assume by contradiction that $L\in CFL$ with pumping constant $p$ and let $\omega = a^p b^p c^p$. Clearly $\omega \in L$ and $\| \omega \| \ge p$. Let $\omega = uvxyz$ a division such that

  1. $\| vy \| > 0$
  2. $\| vxy \| \le p$

Condition 1 stipulates that for every $i \neq 1$ pumping will actually change the substring $vxy$. Condition 2 stipulates that the substring $vxy$ is comprised of at most two type of alphabet symbols. For now we assume that these symbols are $a$ and $b$.

Combine these two facts and we see that for every $i \neq 1$ the string $uv^i xy^i z$ has a different number of $a$'s and $b$'s than $c$'s.

Again, the proof in the book is a bit more complexed, which leads me to think that I might have a mistake here.

Any thoughts? thanks!

$\endgroup$
  • 1
    $\begingroup$ What is the question here? Your question does not include a specific question about a specific part of your attempt. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Raphael Jul 6 '15 at 9:23
4
$\begingroup$

Frankly, I think your argument works. As there is always one of the letters missing, the second condition forces the substring to be "short", pumping will not get equal amounts of $a,b,c$.

For didactical purposes authors in books take extra precautions to make sure the student understands that all cases must be covered. Hence they tend to avoid shortcuts.

$\endgroup$

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