Re: pumping lemma for CFL
- From: "David M Einstein" <Deinst@xxxxxxxxx>
- Date: 2 Nov 2005 12:51:01 -0800
robm wrote:
> thanks for help
> your reply is a concise version of what i have found and now maybe i can
> highlight where my problem is
>
> "Brian" <wray0016@xxxxxxxxxxxxxx> wrote in message
> news:pan.2005.11.02.19.00.39.375993@xxxxxxxxxxxxxxxxx
> > 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.
> >
>
> why is it neccesarily that there is a string |w|<=p in L that can be
> repeated indefinitely and still be in L (other than choosing one that works)
> and be true for all languages
(Note: I tend to be error prone. Take this with at least 1 grain NaCl)
If we have a nonterminal N such that
N -> xNy for some strings x and y not both empty, then
N -> x^j N y^j for all j
now since our grammar is finite if L contains a long enough string then
there must be a nonterminal whose expansion contains itself
>
> and the other problem how one chooses this string since a bad choice
> apparently will not give the desired result
>
> ultimately what mind wrap about pump lemma and RegLang allows one to intuit
> this, as one expects when a sufficient understanding of the concept is
> present
>
> >
> > 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.
>
> so here again it is why /how can we intuit the guarantee that the repetition
> strings are present in L ?
>
> maybe my problem is more basic ?
>
> >
> > 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
> >
.
- References:
- pumping lemma for CFL
- From: robm
- Re: pumping lemma for CFL
- From: Brian
- Re: pumping lemma for CFL
- From: robm
- pumping lemma for CFL
- Prev by Date: Re: Well Ordering the Reals
- Next by Date: Re: Well Ordering the Reals
- Previous by thread: Re: pumping lemma for CFL
- Next by thread: Re: pumping lemma for CFL
- Index(es):
Relevant Pages
|
