Re: pumping lemma for CFL


"Robert Low" <mtx014@xxxxxxxxxxxxxx> wrote in message
news:3ssk38Fpv5seU1@xxxxxxxxxxxxxxxxx
> 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.
>
> This is the pumping lemma for regular languages. The pumping
> lemma for context free languages is a little more complicated,
> and says that L is context free, there 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



.

Relevant Pages

  • whats OOPs jargons and complexities?
    ... in advanced languages such as LISP family, it is not uncommon to define ... subroutine f1 ... For example, in Java, a string is a class String. ...
    (comp.lang.perl.misc)
  • whats OOPs jargons and complexities?
    ... in advanced languages such as LISP family, it is not uncommon to define ... subroutine f1 ... For example, in Java, a string is a class String. ...
    (comp.lang.c)
  • whats OOPs jargons and complexities?
    ... in advanced languages such as LISP family, it is not uncommon to define ... subroutine f1 ... For example, in Java, a string is a class String. ...
    (comp.lang.python)
  • whats OOPs jargons and complexities?
    ... in advanced languages such as LISP family, it is not uncommon to define ... subroutine f1 ... For example, in Java, a string is a class String. ...
    (comp.lang.lisp)
  • Re: pumping lemma (third try)
    ... >> you a string not in L. ... >> contradiction and the proof that L isn't regular breaks down. ... > and answering my wannabe trials and questions. ... > there are no adjacent equal substrings. ...
    (comp.theory)