91Ó°ÊÓ

Pumping lemma can be used for both regular languages and the Context-free

languages. For Context-free languages, it can pump two substrings any number

of times and be in the same language.

Consider the language B=L(G), where G is the grammar as follows,

G = (V,$\underset{}{∑}$,R,S) defined as,$V=\left\{S,T,U\right\};\underset{}{∑}=\left\{0,\#\right\}$ and R is,
$S→TT|U$
$T→0T\left|T0\right|\#$
$U→0U00|\#$

Theorem 2.34, states that the pumping lemma p for the CFL L , is the minimum

length of any string s in the context-free language L such that it may be split into

five pieces s=abⁱ cd^je, that fulfil the following conditions,

The string s is the part of L ,for all $iâ‰\yen 0$

The pumped string b and d must be |bd|>0.

$\left|bcd\right|≤p$

Consider the string s=##0 , with the substring $a=b=\mathrm{θ}=\mathrm{Î\mu }$,c=##,d=0

The pumping length p is ,

|bcd|=|##0|

The theorem conditions are satisfies as follows,

$\left|bd\right|=\left|\mathrm{Î\mu }0\right|$=3 $1â‰\yen 0$

=|0|

. =1, where,

|bcd|=$|\mathrm{Î\mu }\#\#0|$

=|##0|

=3

For $iâ‰\yen 0$ , abⁱ cdⁱe$\mathrm{Î\mu }$L

Consider, i=0, the string s=uv⁰xy⁰z will lie in the language L

. Thus, the theorem

conditions have been satisfied.

Therefore, The minimum values of p that works in the pumping lemma is 3. And the

string satisfies the conditions of the theorem.