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. 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. If a language L {displaystyle L} is context-free, then there exists some integer p ≥ 1 {displaystyle pgeq 1} (called a 'pumping length') such that every string s {displaystyle s} in L {displaystyle L} that has a length of p {displaystyle p} or more symbols (i.e. with | s | ≥ p {displaystyle |s|geq p} ) can be written as with substrings u , v , w , x {displaystyle u,v,w,x} and y {displaystyle y} , such that