In order to decide whether a contextfree language L is infin

In order to decide whether a context-free language L is infinite, the following lemma is useful. A context-free language L is infinite, if and only if there exists some w Element L with p lessthanorequalto |w|

Solution

(I am answering in a manner that helps you understand the solution. When you finally understand the concept, feel free to remove the detailed illustrations.)

In order to prove this, we first state the pumping lemma for CFL :

For every context-free language L

   There is an integer n, such that

      For every string w in L of length > n

         There exists w = abcde such that:

1.|bcd| < n.

2.|bd| > 0.

For all i > 0, ab^icd^ie is in L.

In order to for L to be infinite, it is necessary that we are able to pump some string into strings of L.
For this to happen, the pumping lemma must be satisfied.

Now assume some string w in L

We split w, so as to satisfy the pumping lemma.

w = abcde

Clearly, to pump something into w, w must be greater than p. In other words, w must contain the pumping string. (b^icd^i).

Hence,
|p| = i|b| + |c| + i|d|
and |w| >= |p| as w also contains the length of |a| and |e|


Now according to pumping lemma,

ab^2cd^2e is also in L. We can pump infinitely by increasing the value of i in ab^icd^ie which increases the length of b^icd^i.

w2 = abcde. , w3 = abbcdde, w4 = abbbcddde and so on.

Notice the lengths of successively generated strings.

|w3| = |a| + 2|b| + |c| + 2|d| + |e|

Clearly,
|w3| > 2|p|
Same is also true for all strings generated.
Hence, for L to be infinite, it is necessary that there exists some w whose length is defined by |p| <= |w| < 2|p|.