Re: pumping lemma for CFL


"Robert Low" <mtx014@xxxxxxxxxxxxxx> wrote in message
news:3ssls2FpromiU1@xxxxxxxxxxxxxxxxx
> 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.
>

Thanks for taking time to reply

i am looking at Hopcraft Ullman Sudkamp books at present

I look for Sipser

>
> 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.

This is the kind of description i am looking for , i suppose in reading
this i can see how one might derive this from the more formal definintions
but understanding the formal definitions and significance for purpose of
developing an intuition well thats no so easy (for me)

thanks again for time to respond explain
r


.

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. Where I go wrong?
    ... FOR ALL strings in the language ... Let L be a regular language. ... that every string w in L of length at least n (n be the pumping ...
    (comp.theory)
  • 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)
  • Re: pumping lemma for CFL
    ... you know that uvvwxxy and uvvvwxxxy are in L, ... 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. ...
    (sci.math)