Sipser: Section 2.3
From CSWiki
Contents |
The pumping lemma for context free languages
Introduction
Just as there are languages which can be proven non-regular, there are languages which do not fall under the umbrella of context-free languages. By definition, a non-context-free language is any language that cannot be represented by a pushdown automaton or context-free grammar. The following pumping lemma allows us to prove that a language is not context free.
Proofs that a language is not context-free otherwise proceed in a manner similar to proofs that a language is non-regular, as in Sipser 1.4.
Statement of the Lemma
The pumping lemma for non-context-free-languages, AKA the Bar-Hillel pumping lemma operates on the same basis as the pumping lemma for regular languages. The Bar-Hillel Pumping Lemma
If a language L is context free, there is a pumping length p such that for any string s in the language of at least p length, s can be divided into pieces u,v,x,y,z which satisfy the following:
1. for each,
2. | vy | > 0
3.
A stronger version of the pumping lemma
In Exercise 2.37 of Sipser, we are asked to prove that condition 2 of the pumping lemma can be strengthened, forcing both v and y to be nonempty rather than just one of them. This stronger version might come in handy some time. Of course, we'd have to prove it before we could use it on a homework assignment.
The people behind the theory
Here's a Wikipedia article on Yehoshua Bar-Hillel, for whom this section's pumping lemma is named. According to the article, he was an Israeli mathematician, philosopher, and linguist known for his pioneering work in machine translation.
