Pumping Lemma for CFL and Applications

In the theory of formal languages, the pumping lemma may refer to: Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a sub string that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular.

Content

• What is Pumping Lemma?
• What is CFL?
• Proof of Pumping Lemma using Parse Tree
• Pumping Lemma in CFL and examples
• Applications of Pumping Lemma in CFL

Pumping Lemma

• Pumping Lemma is used to prove language is not regular.
• If A is Regular language, then A has a pumping length ‘P’

such that any string ‘S’ in A has length greater than or

equals to the ‘P’, and which may be divided into 3 parts

S=xyz such that the following conditions must be true

• Conditions

1)xy^iZ belongs to A for every i>=0

2)|y|>0

3)|xy|<=p

What is CFL

• Pumping Lemma for CFL states that for any Context Free Language L, it is possible to find two sub-strings that can be ‘pumped’ any number of times and still be in the same language.
• Pumping Lemma here is used as a tool to prove that a language is not CFL.
• Thus, if L is a CFL, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w, x, y ∈ Σ∗, such that x = uvwxy, and

Conditions

(1) |vwx| ≤ n

(2) |vx| ≥ 1

(3) for all i ≥ 0: uviwxiy ∈ L

Proof using Parse Tree

If all paths in the parse tree of a CNF grammar are of length < m+1, then the longest yield has length 2m-1, as in:

As a path with at least m+1 variables

There are only m different variables, so among the lowest m+1 we can find two nodes with the same label

Fig. 1

Fig. 2

Pumping Lemma in CFL

• w = uvxyz, where vy ≠ ε, |vxy| ≤ p, and for all i ≥ 0, u(v^i)x(y^i)z ∈ L
• We prove a Language is not context-free by applying Pumping Lemma though and finding out a contradiction which violates the lemma.
• We consider 5 cases which can describe possible ways of uvxyz.

For L = {a^i b^j c^k : i < j < k}

1. vxy is a^n for some n<=p, n>=1

2. vxy is a^m b^n for some m+n<=p, m+n>=1

3. vxy is b^n for some n<=p,n>=1

4. vxy is b^n c^m for some m+n<=n, m+n>=1

5. vxy is c^n for some i<=p, i>=1

Example 1: L = {a^Nb^Nc^N|N>0}

Assume L is CFL.

It must have pumping length (say P).

Let’s take a string S = a^Pb^Pc^P.

We have to divide it into 5 parts uvxyz.

P = 4 then S =

If language is CFL, uv^ixy^iz must belong to language.

If i = 2, S = a^6b^4c^5 which does’t belongs to language.

Example 2: L={ ww | w ∈ {0,1}*}

Assume L is CFL.

It must have pumping length (say P).

Let’s take a string S = 0^P1^P0^P1^P.

We have to divide it into 5 parts uvxyz.

P = 5 then S =

If language is CFL, uvixyiz must belong to language.

If i = 2, S = 0^51^70^51^5 which does’t belongs to language.

Applications

1.XML Parsing

Let’s take language (a^n)( b^n)

Above FSM is valid up to n=4.

The problem is that our language didn’t put any constraint on n, and Finite State Machines have to be, well, finite. No matter how many states add to this machine, someone can give me an input where n equals the number of states plus one and my machine will fail. So if there can be a machine built to read this language, there must be a loop somewhere in there to keep the number of states finite.

With these loops added all of the strings in our language will be accepted, but there is a problem. After the first four as, the machine loses count of how many as have been input because it stays in the same state. That means that after four, I can add as many as as I want to the string, without adding any bs, and still get the same return value.

Regular expression can’t parse XML or HTML.

CFL is used.

2. Pumping lemma is used while playing games.

Pumping lemma is a negative test. It can be used in applications like Showing an invalid move in game of chess. As the move may not obey rules of game, pumping lemma can be applied to prove that the inputted move is invalid.

3. At power stations this pumping lemma is used.

Moreover, some Power stations also use this lemma for determining the cut off temperatures to be kept in furnaces. For an example, say pumping lemma can answer to why the temperature shouldn’t go beyond 250 Degrees, etc.

Contributes

Rohan Katkar

Sanket Kawade

Abhita Lakkabathini