Re: pumping lemma for CFL

The "basic" version of the pumping lemma goes more or less like this:

If some language L is regular, then there is some number p (pumping
length), where you can take any string in L of at least length p and
divide it into three strings: x, y, and z, where y is not empty. Then, you
can "repeat" or "pump" y up as many times as you want (>=0) and the
resulting string is in L.

For example, given some string in a language L divided into three parts x,
y, and z:

We have "xyz" being in L. Now, we pump up the string y n times, with n>=0.

n=0 gives us "xz"
n=1 gives us "xyz"
n=2 gives us "xyyz"
n=3 gives us "xyyyz"

etc.

If L is regular, then all these strings have to be in L given that xyz is
in L. If any of these "pumped" strings are NOT in L, then the language is
not regular.

Hope this helps.

On Wed, 02 Nov 2005 16:15:01 +0000, 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
>
> 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

.

Relevant Pages

  • Re: pumping lemma (third try)
    ... >> Duncan's comments and put my hands on a new wannabe trial using the ... >> pumping lemma on the problem below. ... I can decompose a string w belonging to L into x, ... >> being regular without that PL applies, ...
    (comp.theory)
  • Re: pumping lemma for CFL
    ... >> resulting string is in L. ... > not the regular language version. ... yes i am wanting to understnad the CFL pumping lemma exists string in L ...
    (sci.math)
  • Re: How to prove "Cfls are not closed under shuffling"
    ... "If a language L is infinite and ... string w in L with length>= p can be ... Let p be the integer guaranteed by the Pumping Lemma. ... any theorems of the form "If L is context-free, ...
    (sci.math)
  • Re: pumping lemma for CFL
    ... If some language L is regular, then there is some number p (pumping ... resulting string is in L. ... Quite often, even if you pick your test string carefully, the CFL version will require checking a bewildering number of possible cases and making sure you've covered all the bases, as it were, getting a contradiction in every possible case. ...
    (sci.math)
  • Re: trying to use the pumping lemma
    ... Here is my proof using the pumping lemma. ... assume L is a regular language accepted by some DFA M of s states. ... is a string in L that is "long enough" (in your notation, ...
    (comp.theory)