edited by
7,684 views
27 votes
27 votes

For each of the following languages, give the minimum pumping length and justify your answer.

  1. 0001*
  2.  0*1*
  3. 001 ∪ 0* 1*
  4. 0*1$^+$0$^+$1* ∪ 10*1
  5. (01)*
  6. ε
  7. 1*01*01*
  8. 10(11*0)*0
  9. 1011
  10. Σ*
edited by

1 Answer

Best answer
54 votes
54 votes

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 

After watching the above playlist, this question & all questions will become Extremely Simple. So, Let’s begin!!


Pumping lemma states a Deep Property that All Regular languages share. By Showing that a language does not have the property stated by Pumping lemma, we are guaranteed that It is Not Regular. 

Pumping Lemma(PL) is a necessary condition for Regular languages i.e. All Regular languages satisfy this condition But some Non-regular languages also satisfy this condition.


Pumping lemma for Regular languages says

" If a language L is Regular,

then $\exists P \geq 1$, such that 

$\forall \,\,strings\,\,w \in L$, If $|w| \geq P$ then

$\exists x,y,z$, such that $w = xyz$

and $|xy| \leq P$

and $y \neq \in$ i.e. $|y| \geq 1$

and $\forall q \geq 0$, $xy^qz \in L$


In Words, If $L$ is regular, then there’s some magic number $P$(Called Pumping length). And if I take any string $w$ that is at least as long as $P$, then I can break it up into three parts $x, y, $and $z.$ Now, the length of $xy$ is less than or equal to $P$, and also the length of $y$ is greater than or equal to $1$ and less than or equal to $P$.

In very simple words, If $L$ is a regular language then there is some positive number $P$ associated with $L$ such that for all strings $w $ of length greater than or equal to $P$, we can find some non-empty sub-string $y$ in $w$ within the first $P$ symbols of $w$  such that when we repeat $y$ Zero or more times then the produced strings also belong to $L.$


Now coming to Minimum Pumping length(I'll use abbreviation MPL), MPL is the least possible value of $P$ such that Pumping lemma is satisfied by the regular language.

Some Facts :

I recommend to go through the Proof of Pumping lemma for Regular languages or at least the Idea of Pumping lemma based on Pigeon hole principle. Here : https://www.youtube.com/watch?v=vUHJW-OGvFE&list=PLIPZ2_p3RNHjGbysj9OvLTfL2qhsTdsbr&index=4 

1. If you see the intuitive Proof of Pumping lemma(based on pigeon hole principle), You will find that $MPL \leq n$ where $n$ is the number of states in the minimal DFA accepting the regular language. So, If you draw mDFA(minimal DFA) for the given regular language and say the number of states in mDFA is $n$ then you can say that $MPL $ will be less than or equal to $n.$ 

2. MPL will always be strictly greater than the minimal string in the language. (Hint for Proof : Since $y$ can be repeated Zero or more times, When you repeat $y$ Zero times, the string length decreases by at least one symbol) 

3. In the definition of Pumping lemma, $P \geq 1$ so, $MPL \geq 1$

4. If mDFA has a Dead state then $MPL \leq n-1$ (Hint for proof : If there is a Dead state, then all the strings accepted by the mDFA will be among the remaining $n-1$ states, so, if the language is Infinite, then the Loop must be between the remaining states.)

5. If language is Finite then MPL will be $x+1$ where $x$ is the length of the longest string in the language. 

6. If Minimum pumping length for a language is $x$ then any number $\geq x$ is also a Pumping length for the language.

First I'll discuss How to find out MPL for the languages in the question and later I'll discuss some Tricks regarding finding MPL.


$a.$ $r_1 = 0001^*$

So, $L_1 = \{ 000,0001,00011,000111......\}$

For this language, the mDFA will have 5 states, so, $1 \leq MPL \leq 5$, and by fact number $2, $ we can say that $4 \leq MPL \leq 5 .$

Now, You can first try by taking Pumping length as $4$ and if it works then $MPL$ will be $4$, else MLP will be $5.$

For this language, $MPL $ is 4. Take all the strings $w$ of length $\geq 4$ and you can find some non-empty sub-string $y$ in $w$ within the first $4$ symbols of $w$  such that when we repeat $y$ Zero or more times then the produced strings also belong to $L_1.$

Say, $w = 0001$, then $y = 1$

say, $w = 00011$ then $y$ will be the fourth symbol i.e. fourth $1$ ($y$ has to be somewhere within the first 4 symbols of the string because we have assumed Pumping length to be 4.)

So, for any string belonging to this language, You can pick the $y$ to be the fourth symbol of the string and you can repeat this $y$ Zero or more times and the resulted string will belong to the language.

Note 1: For this language, using the Fact 4, you could have gotten the answer as 4 because the mDFA for this language contains a Dead state. So, $4 \leq MPL \leq 4$

Note 2 : For such simple regular expressions you can directly find the MPL. See the regular expression, $0001^*$ so, you can see that $1$ is getting repeated Zero or more times, so , MPL will be 4 as for any string with length greater than or equal to 4, you can find 1 as the fourth symbol and pump it.


$b :$ $r = 0^* 1^*$

$L_2 = \{ \in, 0,1,00,11,01,000,111,001,011....\}$

mDFA for this language will have 3 states, so using Fact 1,4, we can say that $1 \leq MPL \leq 2$ so Now, You can first try by taking Pumping length as $1$ and if it works then $MPL$ will be $1$, else MLP will be $2.$

For this language, $MPL $ is 1. Take all the strings $w$ of length $\geq 1$ and you can find some non-empty sub-string $y$ in $w$ within the first $1$ symbols of $w$  such that when we repeat $y$ Zero or more times then the produced strings also belong to $L_2.$

Say, $w = 0$, then $y = 0$

say, $w = 1$ then $y $ will be the first symbol i.e.  $1$ ($y$ has to be somewhere within the first 1 symbols of the string because we have assumed Pumping length to be 1.)

For any string in this language, $y$ can be the First symbol itself. So, $MPL = 1$


c : $r = 001 + 0^*1^* $

This language is same as $L_2$ so MPL will be 1.


d : $r = 0^*1 + 0 + 1^* + 10^*1$

$L_4 = \{ \in, 0,1,11,01,001,111,101,0001,1111,1001... \}$

The mDFA for this language will have $7$ states, one state is Dead state, so using fact 2,4 we can say that $ 1\leq MPL \leq 6.$ So, start with taking Pumping length as 1 then 2 then 3..etc.. You must be thinking that so many(6) possibilities to check.. And on top of that finding the number of states in  mDFA for this language will take significant amount of time. So what to do?

This language is a Good example for the first Guideline and that "No Need to Construct mDFA to find number of states in it  when construction of mDFA is a tedious task (if mDFA construction is very easy like in previous languages, then go ahead and find the number of states in the mDFA But if mDFA construction is time consuming then Do Not construct mDFA for the language)"  

In case of such languages for which mDFA construction is Time consuming, You can (by practice and experience) directly look at the language and its strings and find MPL. It requires some practice and experience in some cases. 

For this language $L_4, $ MPL is 2. You can pick the string of length $\geq 2$ and check. 


e : $r = (01)^*$

$L_5 = \{ \in , 01,0101,010101... \}$

this is a simple language and MPL for this language is 2. For any string $w $ such that $|w| \geq 2$, you can take the first two symbols i.e. $01$ as $y$ and pump it.


f : $r = \in$

This is a Finite language. And by Fact number 5, MPL will be 1. 


g : $r = 1^*01^*01^*$ 

MPL = 3.


h : $r = 10(11^*0)^*0$

MPL =  4


i : $r = 1011$

By fact 5, MPL = 5.


j : $\Sigma^*$

mDFA will have just 1 state. So, by using Fact 1, MPL = 1.


Also Solve this GATE 2019 Pumping Lemma Question

$\color{Red}{\text{Understand Complete Pumping Lemma, Crystal Clear:}}$

Here is Complete Pumping Lemma Playlist https://www.youtube.com/playlist?list=PLIPZ2_p3RNHjGbysj9OvLTfL2qhsTdsbr 

This Pumping Lemma playlist contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding. 

edited by

Related questions

1 votes
1 votes
1 answer
2