Re: pumping lemma for CFL


"Rick Decker" <rdecker@xxxxxxxxxxxx> wrote in message
news:lN6dnQJWTLE_ivTenZ2dnUVZ_tadnZ2d@xxxxxxxxxxxxxxx
>
>
> Brian wrote:
> > 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.
> >
> <snip>
> >
> > Hope this helps.
>
> It probably won't. The OP was asking for the CFL version,
> not the regular language version.
>

yes i am wanting to understnad the CFL pumping lemma exists string (z) in L
that can be sub-divided into (uvwxy) where vx not empty bla bla but i can
kind of use the RL version to illustrate the nature of my problem in
capturing the CFL bits as i have doen in other post

>
> Regards,
>
> Rick
>
>
> To robm (the OP),
>
> I sympathize with you; the PL for CFLs has a good side and a bad side.
> On the good side, the proof of the PL is both elegant and fairly
> easy to understand. If that's what's giving you problems, tell
> us where you're stuck and we can help. On the other hand, *using*
> the PL to show that a language isn't a CFL is usually much
> trickier than the regular language version. 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. If your problems lie
> there, give an example where you're stuck and (if you're lucky)
> you may be able to get a detailed explanation.
>
> BTW, for problems like this, the comp.theory NG might be a more
> appropriate place to ask for help.
>
>
> R.,
>
> R.
>


.

Relevant Pages

  • Re: pumping lemma for CFL
    ... The "basic" version of the pumping lemma goes more or less like this: ... resulting string is in L. ... For example, given some string in a language L divided into three parts x, ... If L is regular, then all these strings have to be in L given that xyz is ...
    (sci.math)
  • Re: Proving a Language Is Not a CFL
    ... If A is a CFL and B is a regular language, then the intersection of A ... is not a CFL. ...
    (comp.theory)
  • 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: pumping lemma for CFL
    ... >> resulting string is in L. ... > ultimately what mind wrap about pump lemma and RegLang allows one to intuit ... >> For example, given some string in a language L divided into three parts x, ... >> If L is regular, then all these strings have to be in L given that xyz is ...
    (sci.math)
  • Re: A CFG for a CFL
    ... >> The language ... regular, but for a given alphabet A, if |A|> 1 then the language ... > You want a CFL over the alphabet ...
    (comp.theory)