Pumping Lemma For Context-free Languages - Usage of The Lemma

Usage of The Lemma

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

For example, we can show that language is not 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 is in for every integer . By our choice of and the fact that, it is easily seen that the substring can contain no more than two distinct letters. That is, we have one of five possibilities for :

1. for some .
2. for some and with .
3. for some .
4. for some and with .
5. 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. There are more powerful proof techniques available, such as Ogden's lemma, but also these techniques do not give a complete characterization of the context-free languages.