Pumping lemma for CFG

The pumping lemma for CFGA context-free grammar (CFG) is a set of recursive rules used to form strings of a particular context-free language. is a well-built theorem that proves a language is not CFLA context-free language (CFL) is a language generated by a context-free grammar..

Formal theorem

The pumping lemma states:

For any context-free language L, there exists an integer n, such that for all $x ∈ L$ with $|x| ≥ n$, there exists $v, w, x, y, z ∈ Σ^∗$, such that $x = vwxyz$, and

1. $|wxy| ≤ n$

2. $|wy| ≥ 1$

3. for all $i ≥ 0: vw^ixy^iz ∈ L$

The given rules mean that if two substrings from a string of a CFL are pumped i.e., parts w and y are repeated i number of times, it will still remain a part of the CFL.

The lemma gives a result in the form of a contradiction. We suppose that a given instance (string) of a language is context-free, and we contradict our supposition, as the pumped string will not be a part of the language.

Note: This lemma does not show if a language is context-free.

Steps of the lemma

The following steps are involved in applying lemma:

1. Given a context-free language, extract a string (instance) from it.

2. Divide the string into substrings such that $|wxy| ≤ n$ and $|wy| ≥ 1$.

3. Find a suitable i where the pumped string does not remain a part of the language.

Examples

• Let $L={ww | w ∈ (0, 1)^*}$ and suppose L is context-free language.

  Take $u=0^n 10^n 1$ where $|u| = 2n+2 > n$ and $u ∈ L$

  We divide u in such a way that $v=\epsilon, wxy = 0^n$ where $|wxy|≤ n$ $(w = 0^{n/2} , x=^ , y = 0^{n/2})$ and $(w = 0^{n/2} , x=^ , y = 0^{n/2})$.

  Taking i = 0:
$vw^ixy^iz = (1)(0^{n/2})^0 (\epsilon) (0^{n/2})^0 (10^n1)$

        $= 10^n1 ∉ L$
As the string is not a part of the language, so we can say that our initial supposition is wrong and that the language L is non-context-free.

• Let's take another example:

   $L={a^i b^j c^k | i = j \space or \space i= k}$ and suppose L is context-free language.

  Take $u=a^nb^n c^n$ where $|x| = 3n> n \space(n=i=j=k)$ and $x ∈ L$

  We divide x in such a way that $v=\epsilon, wxy = a^n \space where \space |wxy| \leq n \space (w=a^{n/2}, x=\epsilon,y=a^{n/2})$and $w = b^nc^n$

  Taking i = 0:
$vw^ixy^iz = (1)(a^{n/2})^0 (\epsilon) (a^{n/2})^0 (b^nc^n)$

        $= b^nc^n ∉ L$
As the string is not a part of the language, so we can say that our initial supposition is wrong and that the language L is non-context-free.