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.


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

Relevant Pages

  • Re: Operator overloading in C
    ... All development of C as an independent language has ... making any changes or improvements to the standard ... The lack of a counted string data structure, ... Pointers can't be used for arg1 or arg2. ...
    (comp.std.c)
  • Re: syntax...
    ... B&D on the part of the language designer. ... probably handle concatenation of string literals by itself, ... bitwise XOR, or if not that, then exponentiation.) ...
    (comp.lang.misc)
  • Why C Is Not My Favourite Programming Language
    ... C has no string type. ... compiler take care of the rest. ... Why does any normal language ... the programmer fail. ...
    (comp.lang.c)
  • Re: Controlling Javascript from server side
    ... but five different language implementations here. ... 'true' means that the request must be handled asynchronously. ... There is exactly *no* reason for such a thing here. ... | percent-endoded string). ...
    (comp.lang.javascript)
  • Re: Theodore Adorno, a prophet of data systems design
    ... C may not be a forgiving language, ... >> attention get burned with the memory leaks, and buffer overruns, ... by a small, compact team of brilliant programmers, or it may be ... so you agree that it is not a limit on the length of the string, ...
    (comp.programming)