Informal Statement and Explanation
The pumping lemma for context-free languages (called just "the pumping lemma" for the rest of this article) describes a property that all context-free languages are guaranteed to have.
The property is a property of all strings in the language that are of length at least p, where p is a constant—called the pumping length—that varies between context-free languages.
Say s is a string of length at least p that is in the language.
The pumping lemma states that s can be split into five substrings, where vy is non-empty and the length of vxy is at most p, such that repeating v and y any (and the same) number of times in s produces a string that is still in the language (it's possible and often useful to repeat zero times, which removes v and y from the string). This process of "pumping up" additional copies of v and y is what gives the pumping lemma its name.
Note that finite languages (which are regular and hence context-free) obey the pumping lemma trivially by having p equal to the maximum string length in L plus one. As there are no strings of this length the pumping lemma is not violated.
The pumping lemma is often used to prove that a given language is non-context-free by showing that for each p, we can find some string s of length at least p in the language that does not have the properties outlined above, i.e. that it cannot be "pumped" without producing some strings that are not in the language.
Read more about this topic: Pumping Lemma For Context-free Languages
Famous quotes containing the words informal, statement and/or explanation:
“We as a nation need to be reeducated about the necessary and sufficient conditions for making human beings human. We need to be reeducated not as parents—but as workers, neighbors, and friends; and as members of the organizations, committees, boards—and, especially, the informal networks that control our social institutions and thereby determine the conditions of life for our families and their children.”
—Urie Bronfenbrenner (b. 1917)
“Truth is that concordance of an abstract statement with the ideal limit towards which endless investigation would tend to bring scientific belief, which concordance the abstract statement may possess by virtue of the confession of its inaccuracy and one-sidedness, and this confession is an essential ingredient of truth.”
—Charles Sanders Peirce (1839–1914)
“Herein is the explanation of the analogies, which exist in all the arts. They are the re-appearance of one mind, working in many materials to many temporary ends. Raphael paints wisdom, Handel sings it, Phidias carves it, Shakspeare writes it, Wren builds it, Columbus sails it, Luther preaches it, Washington arms it, Watt mechanizes it. Painting was called “silent poetry,” and poetry “speaking painting.” The laws of each art are convertible into the laws of every other.”
—Ralph Waldo Emerson (1803–1882)