Pumping Lemma For Context-free Languages - Informal Statement and Explanation

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.