Re: pumping lemma for CFL

robm wrote:
> sorry for amateur question but...
> can someone give links to info that helps one capture/grasp the pumping
> lemma for CFL ? i am missing something, some basic **important** aspect
> that preventing me from going from following an example to applying it to
> solutions
>
> I've looked at three books, one practical approach tries to describe plus
> define but the explanation seems to make big leaps in my amateur
> misunderstanding mind, and then two very formal math oriented with very
> succinct definitions and compact proofs and examples

My suggestion would be for you to take half a step back. Take
an example of a simple non context free language (one of the
examples from the book will probably be perfect), forget about
the pumping lemma, and try to construct a finite automaton that
recognizes it. Once you understand why you are failing at this
impossible task, read the proof of the pumping lemma. It
should make more sense. Once you understand the proof, walk
through one of the book examples, but replace the reference to
the pumping lemma with an instance of its proof.

Very formal math oriented books expect to be read very slowly.
It is important to understand the definitions and the proofs.
If you do not understand a proof, it often helps if you run
through the proof using an example (that is one of the reaons
that authors provide examples (and exercises).

The crucial point in the pumping lemma is that if you visit
more than the number of states in a DFL, you had to have
visited the same state twice.


>
> I've looked at these web sites and others which give similar definition and
> description but no example that helps my mind capture the essence of the
> pumping Lemma
>
> en.wikipedia.org/wiki/Pumping_lemma
> www.cs.brandeis.edu/~mairson/poems/node1.html
> www.cs.may.ie/~jpower/Courses/parsing/node41.html
> www.cs.wpi.edu/~alvarez/CS3133/pumping.html
>
> TIA for any helpful info
> r

.