What is the minimum pumping length of the following languages

Question

This is from the first chapter questions of Sipser's book on TOC. I am stuck in some of the questions where we are asked to find the pumping length of the following languages. 

Find the minimum pumping length of the following regular languages:-

1. L=$0^*1^+0^+1^* \cup \ 10^*1$ 

2. L=001 U 0*1* 

3. L=0*1*
4. L=10 (11* 0)* 0 
5. L= ∊

Comments

@Arjun Sir and @Praveen Saini Sir plz help ! I really need to clear these concepts ! Atleast, if possible , give some hints !

---

one more explanation https://gateoverflow.in/303738/michael-sipser-exercise

---

To solve any Pumping Lemma based question, First, Understand Pumping Lemma. Clear, Correct & Complete Understating is Needed.

Here is the $\color{red}{\text{Complete “Pumping Lemma for Regular Languages” Playlist}}$, with Proof, Questions, Variations & Results  etc..

Complete Pumping Lemma Playlist, with A Lot of Questions: https://www.youtube.com/playlist?list=PLIPZ2_p3RNHjGbysj9OvLTfL2qhsTdsbr  

Answer 1

(Definition) If L is a regular language, then there is a number p (the pumping length) such that s is any string in L of length p or more can be written as s = xyz, satisfying the following conditions :

1. for each i$\geq$ 0 , xyⁱz ∈L,

2. |y|>0, and 

3. |xy|$\leq$p.

So we need to find the minimum length string s = xyz ∈ L such that xyⁱz should also be L.
Remember:     

 i) y $\neq$ ∊ , point 2 of definition  |y|>0 means only that.

  ii) y should be in closure (loop) that repeats ,so that we get xyⁱz∈L
  iii) Don't Worry about Unions, only we need to find s = xyz ∈L that satisfying i) and ii) above said. 

Now 

Q1. 0*1⁺0⁺1* U 10*1

s= xyz =101 , where x=1 , y=0 and z=1  such that xyⁱz∈L ( that is 10*1, look i >=0)

Minimum Pumping length = 3
( if you are confused that 11 in L and have minimum length, then remember point2 of definition y $\neq$ ∊ and secondly when you will put i=0 in xyⁱz you will get 11 ∈L )
 

Q2. L = 001 U 0*1* 

s= xyz = 0 , where x=∊,y=0 and z=∊ such that xyⁱz∈L (that is 0*∊)

Minimum Pumping length = 1

Q3. L = 0*1* 

Minimum Pumping Length = 1 (refer Q2)

Q4. L = 10(11*0)*0

s = xyz = 10100 where x=10,y=10 and z=0 such that xyⁱz∈L (that is 10(1∊0)*0  )

Well it looks Minimum Pumping length is 5 , But it is not, We can repeat y any time (or it should be) and y$\neq$ ∊ that mean we cannot use 3 or less length string from L for pumping , So y can be 10 (minimum) so minimum string S we using for pumping is 10100  of length 5, but length 4 string can not generated from the given language (that's not our fault). So we can say we use 4 or more length string s for pumping that belongs to L. 

So Minimum Pumping length = 4.

Q5.  L= ∊

Ideally its length 0 only s = xyz = ∊, where x = ∊ , y = ∊ and z = ∊ But y$\neq$ ∊ 

So we say, Minimum pumping length = 1 . 

Comments

What's the intuition behind choosing a proper s ?

---

I think it is written

s= xyz  such that y should make closure (left of that closure is x , and right is z) and y $\neq$ ∊ and that (string s) should be of minimum possible length

L =10*1   so y should repeat and y $\neq$∊ so y =0 , x =1 and z =1 s= xyz =101

---

Got it ! thank you so much for your help. much appreciated !

---

@Praveen Saini ​sir, can I take s=xyz=100 in Q2 ?

---

No , as 100 doesn't belong to L given in Q2.

it should be either 0 or 1 , minimum length and belong to L

---

Sorry ,sir i was asking for Q4 by mistake i wrote Q2.

---

I think No, as in s= xyz , we are pumping with the help of y (that repeats), and y $\neq$ ∊ and yes during pumping xyⁱz when we put i = 0 we get 100 ∈ L

---

Q5.  L= ∊

Here if we take  s = xyz = ∊, where x = ∊ , y = ∊ and z = ∊ 

then  y = ∊ => |y|>0 is not satisfied.

So how can we say pumping length = 1 ??

 

---

It is a case where no "w=xyz" exist with condition y $neq$ 0

so we can say any number can be pumping length.

In case of minimum pumping length we cannot chose $0$ bcoz $|y|$ should be $ \geq 0$ . So we say it is $1$

---

But how can we verify the fact that if a language is regular,it definitely satisfy Pumping Lemma ?

Here L  = ∊ is regular so it must satisfy pumping lemma..rt?

---

yes , you are right.

but it is just like  P implies Q

if P is true, then Q is.

if P is not true, we can't say Q is false.

---

Yes, my doubt is :

here language is regular...so why it does not satisfy pumping lemma?

because if language satisfy pumping lemma ,it may or maynot be regular.But if language is regular,it must satisfy pumping lemma.

So here language is regular,so it must satisfy but here it is not satisfying..why??? 

---

Your doubt is valid

 we can't apply these rule on finite language, as we are not pumping anything

so Ideally you and I can say, minimum pumping length is 0, but we are not allowed to say that too.

so we say here minimum pumping length is $1$. (even we are not pumping anything)

---

In case of finite RL, can't we say that we are pumping only finite no, of strings i.e we are using only some finite values of i>=0.

But for infinite RL, we are pumping infinite no. of strings since i>=0.

---

man this is totally wrong
pumping means find y in xyz , such that we can repeat that y to get xy^iz for i>=0 , it is for all i 
once we can repeat that y, anytime , then how can language will be finite.

---

yes for finite languages, pumping length "n" is big enough to take in all the strings in L without requiring a loop in corresponding DFA.

Language containing empty string obeys pumping lemma rt? We cannot get any "w" but pumping lemma says "if such a w exist", so it is not violating pumping lemma.

---

Yes ,here there is no such 'w' which we can use for checking pumping lemma.So what is the point in asking pumping length..?

In context of FA, pumping length refers to no. of min. no of states required to accept the strings  in the given language.So since no of state required to accept L = ∊ is 1. So can we say that pumping length is '1'

---

@arjun yes there is no "w" exist with such condition :) my mistake , I said it doesn't apply

---

Yes ,here there is no such 'w' which we can use for checking pumping lemma.So what is the point in asking pumping length..?

In context of FA, pumping length refers to no. of min. no of states required to accept the strings  in the given language.So since no of state required to accept L = ∊ is 1. So can we say that pumping length is '1'

---

it looks correct to me.

---

k.....thanx!

---

@Praveen Saini  Sir,
Could you explain pumping lemma for CLF its basic conditions like this ?

 

---

Sir in Q4 how did u conclude that string length 3 or less not possible ?
y=10

So string length 2 or less is not possible is acceptable to me

How can puping length be 4 if length of string 4 cannot be derived from the Language

s= xyx |s|= n ..> pumpimg length
is l does not belong to S then how can pumping length be identified >?

---

$y$ cannot be $\epsilon$ that's why we cannot use length 3 or less string for pumping. 

and for second part, refer comment above by arjun.  

length 4 strings satisfies pumping lemma. 

---

Sir i didn't get u . What is the string with length 4 here ? I didn't get you . if such a language exists then what is its x y z part ?

---

if there is a string exists then we need to find x, y, z and all these conditions.

otherwise then there is no need

---

@Praveen sir In question 1 and question 4 why your views do differ? I mean if that is the case then question 1 should have  2 as minimum pumping length. Can you please check this link.. why answers are differing

http://stackoverflow.com/questions/33028105/minimum-pumping-length-for-the-following-regular-languages

---

@Praveen Saini

Sir

here Q2 will be 4, 

right?

https://gateoverflow.in/302833/gate2019-15

---

I think 1 is correct Bcoz 001 is subset of 0*1*

---

why in question no 1    Q1. 0*1^+0^+1* U 10*1    you have  not taken  s= 010 ,instead you choose s= xyz =101 ,

---

@Praveen Saini sir 

In 4.   L =. 10(11*0)*0

how min pumping length is 4...

​​ eventually length 4 is not generate ...

plz explain

---

@Praveen Saini  ,  Can you please explain for Q.4 why 

Minimum Pumping length = 4. ???

---

@Sandeep Verma you can take example distribute your string 010 in form  x y^i z and put i=0. the string which will be generated will not be part of your language, hence you can not take 010.  

---

https://gateoverflow.in/302833/gate2019-15

@Praveen Saini In this question’s answer by Sachin Mittal 1, he said that

“Pumping length for a regular language makes sure that any string in that language with the length greater than pumping length has some repetition.”

 

But in 1^st question , you answered pumping length = 3, but 0101 is a string possible without any repetition , but for more than 4 , you have to repeat, so should not the answer be 4??

---

Please correct me if I’m wrong

3) L=10 (11* 0)* 0

Minimum pumping length = 3

Take S = 100, x = $\epsilon$, y = 10, z = 0 and |y| > 0 and |xy| <= 3

Then for every i, x$y^{i}$z $\epsilon$ L

We can divide the same way for every string w, |w| $\epsilon$ L

 

---

such a nice explanation praveen.

loved your work

Thanks man