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 are now a nation of people in daily contact with strangers. Thanks to mass transportation, school administrators and teachers often live many miles from the neighborhood schoolhouse. They are no longer in daily informal contact with parents, ministers, and other institution leaders . . . [and are] no longer a natural extension of parental authority.”
—James P. Comer (20th century)
“The new statement will comprise the skepticisms, as well as the faiths of society, and out of unbeliefs a creed shall be formed. For, skepticisms are not gratuitous or lawless, but are limitations of the affirmative statement, and the new philosophy must take them in, and make affirmations outside of them, just as much as must include the oldest beliefs.”
—Ralph Waldo Emerson (1803–1882)
“Natural selection, the blind, unconscious, automatic process which Darwin discovered, and which we now know is the explanation for the existence and apparently purposeful form of all life, has no purpose in mind. It has no mind and no mind’s eye. It does not plan for the future. It has no vision, no foresight, no sight at all. If it can be said to play the role of the watchmaker in nature, it is the blind watchmaker.”
—Richard Dawkins (b. 1941)