Re: pumping lemma for CFL

robm wrote: 
"Robert Low" <mtx014@xxxxxxxxxxxxxx> wrote in message
 The pumping
lemma for context free languages ...
says that [if] L is context free, there [should have been then]
>>there is some number 
p such that a string longer than p is uvwxy where |vwx|
is no longer than p, and v and x can be repeated as many times
as you want  and the result is in L.

Note that v and x must both be repeated the same number
of times: you know that uvvwxxy and uvvvwxxxy are in L,
but you don't know about uvvwxxxy.

which underscores my difficulty in trying to intuit from what i am reading 

I like Sipser's book 'Introduction to the theory of computation'.
Very clearly explained, without getting bogged down in technical
detail. If you can get at a copy, it might help.

There are also web resources, such as

http://en.wikipedia.org/wiki/Pumping_lemma

but I don't know how helpful you'll find them.

In my mind the *essence* of the pumping lemmas is
that a long enough string in a simple enough language
has a segment that can be repeated arbitrarily often
while remaining in the language. In the regular
case, it's a single segment, and in the context free
case the segment may be broken by a bit in the
middle that doesn't get repeated.

Whether my intuitive picture will help you is hard to
say: but you're welcome to try it on for size.
.

Relevant Pages

  • context free languages under SCRAMBLE operation
    ... For strings w and t, write w =' t if the symbols of w are a permutation of the symbols of t. ... which accepts the regular language to be scrambled can simply have its state transitions re-arranged to accept the SCRAMBLE of the language. ... This is de facto context free since every regular language is in turn context free. ...
    (comp.theory)
  • Re: pumping lemma for CFL
    ... >>>lemma for context free languages ... ... >>>p such that a string longer than p is uvwxy where |vwx| ... > In my mind the *essence* of the pumping lemmas is ... > while remaining in the language. ...
    (sci.math)
  • Re: need help developin better sense for context free languages
    ... Are there any tell tale signs that it is/is not context free? ... Is there an easy way to tell starigh away if a language is context free ... tested on the use of closure properties to determine ... K chosen as the right one to use?"), With a little practice with those ...
    (comp.theory)
  • Re: need help developin better sense for context free languages
    ... Is there an easy way to tell starigh away if a language is context free ... side conditions on equality of substrings or lengths of substrings, ... tested on the use of closure properties to determine ...
    (comp.theory)