Question

Consider the language B=L(G), where Gis the grammar given in

Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34,

states the existence of a pumping length p for B . What is the minimum value

of p that works in the pumping lemma? Justify your answer.

Short answer

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

Step-by-step solution

Explain Pumping Lemma

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.

What is the minimum value of p that works in the pumping lemma?Justify your answer.

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

G = (V,$\sum _{}$,R,S) defined as,$V=\left\{S,T,U\right\};\sum _{}=\left\{0,\#\right\}$ and R is,
$S\to TT|U$
$T\to 0T\left|T0\right|\#$
$U\to 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\ge 0$

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

$\left|bcd\right|\le p$

Consider the string s=##0 , with the substring $a=b=\theta =\epsilon$,c=##,d=0

The pumping length p is ,

|bcd|=|##0|

The theorem conditions are satisfies as follows,

$\left|bd\right|=\left|\epsilon 0\right|$=3 $1\ge 0$

=|0|

. =1, where,

|bcd|=$|\epsilon \#\#0|$

=|##0|

=3

For $i\ge 0$ , abⁱ cdⁱe$\epsilon$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.