Re: pumping lemma for CFL



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.


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
    ... >> 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: 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
    ... >> 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)
Quantcast