Pumping Lemma For Context Free Languages - CFL

  

Pumping Lemma for Context-Free Languages

Let LL be an infinite context-free language.
Then there exists some positive integer mm such that any

ωL with ωm\omega \in L \text{ with } |\omega| \ge m

can be decomposed as

ω=uvxyz\omega = uvxyz

such that

  1. vxym|v x y| \le mPumping portion is small

  2. vy1|v y| \ge 1Length of middle section is bounded

  3. uvixyizLuv^i x y^i z \in L for all i=0,1,2,… Pumping preserves membership



Intuitive Explanation 

  • The lemma tells us that long enough strings in any context-free language must contain a portion that can be "pumped" (repeated or deleted) and still produce valid strings in the same language.

  • This happens because context-free grammars have finite sets of variables but can generate infinite strings.

  • So, when we derive a very long string using a parse tree, some variable must repeat along some path in the tree.

  • This repeated variable allows us to repeat or remove the corresponding part of the string — giving the “pumping” property.



Proof 

Consider the language L{λ}L - \{\lambda\}, and let G=(V,T,S,P) be a context-free grammar for LL without λ-productions or unit-productions.

Let the maximum length of the right-hand side of any production in GG be kk.
That is, for each production AαP, we have αk.

Since LL is infinite, it has derivations of arbitrarily long length and hence derivation trees of arbitrarily large height.


Step 1: Repetition of a variable along a path

Let the number of variables in GG be nn.
In any derivation tree of height greater than nn,
there must be some variable that repeats on a single path from the root to a leaf (by the pigeonhole principle).

Suppose a variable AA occurs twice along a path,once near the top and once lower down.

Schematically, the derivation has the form:

SuAzuvAyzuvxyzS \Rightarrow^* u A z \Rightarrow^* u v A y z \Rightarrow^* u v x y z

where u,v,x,y,zu, v, x, y, z are strings of terminals.


Step 2: Structure of the repeated variable

From this derivation we see:

AvAyA \Rightarrow^* v A y

and

AxA \Rightarrow^* x

Thus, the variable AA can derive a string containing itself (surrounded by vv and yy),
and it can also derive a string xx consisting only of terminals.

This gives the pattern that allows “pumping” of the substrings vv and yy.


Step 3: Pumping mechanism

Replacing the lower occurrence of AA with its derivation repeatedly yields:

SuAzuvAyzuvvAyyzS \Rightarrow^* u A z \Rightarrow^* u v A y z \Rightarrow^* u v v A y y z \Rightarrow^* \cdots

Finally, replacing the last AA by xx gives the sequence of strings:

uvixyiz,i=0,1,2,u v^i x y^i z, \quad i = 0, 1, 2, \ldots

Each of these strings is generated by GG, and therefore belongs to LL.


Step 4: Bounds on the substring lengths

Since the grammar GG has a finite number of variables and each production is of finite length, the size of the section between the two occurrences of AA in the derivation tree can be bounded by some integer mm.

Thus, we can ensure that:

vxym|v x y| \le m

and, because GG has no λ-productions or unit-productions, both vv and yy cannot be empty simultaneously:

vy1|v y| \ge 1

Step 5: Conclusion

Hence, for every ωL\omega \in L with ωm|\omega| \ge m,
we can decompose it as ω=uvxyz\omega = u v x y z satisfying:

  1. vxym|v x y| \le m

  2. vy1

  3. uvixyizLu v^i x y^i z \in L, for all i0

This completes the proof.




🧠 Key Takeaways 

PropertyExplanation
Purpose        The pumping lemma for CFLs is used to prove that a language is not context-free.
Based on        Repetition of variables in long derivations (parse tree argument).
Limitations        It gives a necessary, but not sufficient, condition — i.e., some non-CFLs may still            satisfy it.
Main idea        Strings in a CFL can be “pumped” in two places (v,y) while remaining valid.



Comments

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

Non deterministic Finite Automata NFA

Formal Definition - Turing Machine