Pumping lemma for context-free languages
In computer science, in particular in formal language theory, the pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property shared by all context-free languages and generalizes the pumping lemma for regular languages. The pumping lemma can be used to construct a proof by contradiction that a specific language is not context-free. Conversely, the pumping lemma does not suffice to guarantee that a language is context-free; there are other necessary conditions, such as Ogden's lemma, or the Interchange lemma. Formal statement 

If a language  is context-free, then there exists some integer  (called a "pumping length") such that every string  in  that has a length of  or more symbols (i.e. with ) can be written as

 

with substrings  and , such that

 1. ,
 2. , and
 3.  for all . Below is a formal expression of the Pumping Lemma. 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 , where  is a constant—called the pumping length—that varies between context-free languages. Say  is a string of length at least  that is in the language. The pumping lemma states that  can be split into five substrings, , where  is non-empty and the length of  is at most , such that repeating  and  the same number of times () in  produces a string that is still in the language. It is often useful to repeat zero times, which removes  and  from the string. This process of "pumping up"  with additional copies of  and  is what gives the pumping lemma its name. Finite languages (which are regular and hence context-free) obey the pumping lemma trivially by having  equal to the maximum string length in  plus one. As there are no strings of this length the pumping lemma is not violated. Usage of the lemma 

The pumping lemma is often used to prove that a given language  is non-context-free, by showing that arbitrarily long strings  are in  that cannot be "pumped" without producing strings outside . For example, if  is infinite but does not contain an (infinite) arithmetic progression, then  is not context-free. In particular, neither the prime numbers nor the square numbers are context-free. For example, the language  can be shown to be non-context-free by using the pumping lemma in a proof by contradiction. First, assume that  is context free. By the pumping lemma, there exists an integer  which is the pumping length of language . Consider the string  in . The pumping lemma tells us that  can be written in the form , where , and  are substrings, such that , , and  for every integer . By the choice of  and the fact that , it is easily seen that the substring  can contain no more than two distinct symbols. That is, we have one of five possibilities for :

  for some . for some  and  with 
  for some . for some  and  with . for some . For each case, it is easily verified that  does not contain equal numbers of each letter for any . Thus,  does not have the form . This contradicts the definition of . Therefore, our initial assumption that  is context free must be false. While the pumping lemma is often a useful tool to prove that a given language is not context-free, it does not give a complete characterization of the context-free languages. If a language does not satisfy the condition given by the pumping lemma, we have established that it is not context-free. On the other hand, there are languages that are not context-free, but still satisfy the condition given by the pumping lemma, for example
 
for  with e.g. j≥1 choose  to consist only of b’s, for  choose  to consist only of a’s; in both cases all pumped strings are still in L.

A precursor of the pumping lemma was used in 1960 by Scheinberg to prove that  is not context-free. References 

  — Reprinted in: 
  Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119. Formal languages
Lemmas