Pumping lemma for context-free languages

From Wikipedia, the free encyclopedia

The pumping lemma for context-free languages, also known as the Bar-Hillel lemma, is a lemma that gives a property that all context-free languages have. Its primary use is to prove a language is not context-free.

The pumping lemma for context-free languages cannot be used to prove that any arbitrary non-context-free language is not context-free. In some cases the more generalized Ogden's lemma must be used.

Contents 1 Formal statement 2 Use of lemma 3 See also 4 References

[edit] Formal statement

If a language L is infinite and context-free, then there exists some integer p > 0 such that any string w in L with |w| ≥ p (where p is a pumping length) can be written as

w = uvxyz

with strings u, v, x, y and z, such that |vxy| ≤ p, |vy| ≥ 1, and

uv ⁱxy ⁱz is in L for every integer i ≥ 0.

[edit] Use of lemma

The pumping lemma for context-free languages can be used to show that certain languages are NOT context-free.

We can show that the language L = {a^jb^jc^j, j>0} is NOT context-free.

1. Suppose L is context-free
   1. Conditions:
      1. | vxy | ≤ p. That is, the middle portion is not too long.
      2. vy ≠ ε (empty). Since v and y are the pieces to be “pumped”, this condition says that at least one of the strings we pump must not be empty.
      3. For all i ≥ 0, uvⁱxyⁱz is in L. That is, the two strings v and y may be “pumped” any number of times, including 0, and the resulting string will still be a member of L.
2. If string w ∈ L where | w | > p, it follows that w = uvxyz, where | vxy | ≤ p
3. Now, choose a value for j that is greater than p.
4. Then, wherever vxy occurs in the string a^jb^jc^j, vxy cannot contain more than two distinct letters, since the rightmost a is j+1 positions away from the leftmost c.
   1. Ex: It can be all a’s, all b’s, or all c’s, or it can be a’s and b’s, or it can be b’s and c’s.
      1. Thus, the string vxy cannot contain more than two distinct letters, but by the pumping lemma it cannot be empty either, so it must contain at least one letter.
5. Now we can start "pumping"
   1. Since uvxyz is in L, uv²xy²z must also be in L. Since v and y can’t both be empty, | uv²xy²z | >
      | uvxyz |, so we have added letters.
      
   2. But since vy does not contain all three distinct letters, we cannot have added the same number of each letter. We have pumped more letters and contradicted the original definition of L. Thus,
      uv²xy²z cannot be in L.
      
6. We have arrived at a contradiction. Therefore, our original assumption, that L is context free, is false.  KJ
   

[edit] See also

• Pumping lemma for regular languages
• Formal languages
• Ogden's lemma

[edit] References

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 1.4: Nonregular Languages, pp.77–83. Section 2.3: Non-context-free Languages, pp.115–119.