The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
340 views
For each of the following languages, give the minimum pumping length and justify your answer.

a. 0001*

b. 0*1*

c. 001 ∪ 0* 1*

d. 0*1$^+$0$^+$1* ∪ 10*1

e. (01)*

f. ε

g. 1*01*01*

h. 10(11*0)*0

i. 1011

j. Σ*
in Theory of Computation by Junior (857 points)
edited by | 340 views

1 Answer

+7 votes
Best answer

NOTE : The Question Was Not Properly written when I answered it in the first place. So, Consider the answer for the languages I have written in the answer.


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 : http://www.ling.upenn.edu/courses/Fall_2003/ling106/PumpingLemma.pdf

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.

by Boss (25.1k points)
edited by
0

thanks for the brief explanation, but I've some doubt 

Doubt 1.

In the definition of pumping lemma mentioned above if we put  q=0, then w=xyz will become w=xz
will it not fails condition which says 'y' must be at least 1 in length. meaning the condition should be ∀q≥1∀q≥0, xyqz∈L

Correct me where I'm wrong.

Doubt 2. Pumping lemma is for Regular language, Pumping lemma works fine for 'infinite languages' but when it comes to the 'finite language' it doesn't fit with the definition.

e.g. Pumping length what I understood is "Pumping length for a regular language makes sure that any string in that language with the length greater than pumping length has some repetition." 

now take this example(e.g i) L=1011

you said MPL=5 and by definition, there is no string in the language with the length greater than MPL i.e. 5. and there is no loop in our language. how does pumping lemma working fine with finite languages?

Can you elaborate this fact a little bit -

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

 

 

+1

In the definition of pumping lemma mentioned above if we put  q=0, then w=xyz will become w=xz 
will it not fails condition which says 'y' must be at least 1 in length.

No. $y$ must be of length $\geq 1$ But $q$ is the power of $y.$ And any string power $0$ is $\in.$

Remember $y \geq 1$ and $q \geq 0$

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

Pumping lemma says that for $every$ Regular language $L$, there exists a magical number $P$ such that $if$ $|w| \geq P$ then $w$ can be pumped (where $w \in L$ )

Focus on $if.$

0
Got it....but for e.g  d : r=0∗1+0+1∗+10∗1           I'm getting MPL as 3.
0

what is + in question d ?

is it union or positive closure ?

before i edit the question, it is like union but not positive closure ! @KULDEEP SINGH 2

if it is union, then minimum pumping length is 2, else it is 3 !

0

can you please tell in question number d how did you determine number of states in minimal DFA will be equal to 7. the mDFA is difficult to construct as you have mentioned @Deepakk Poonia (Dee)

 

and why is MPL=1 in question j?

0

Please edit the question it is Union, not positive closure.

And I still have doubt for (d.) 

r = 0*1 + 0 + 1* + 10*1 

let me break it down as :

r1= 0*1  ,   r2= 0

r3= 1*    ,   r4= 10*1

so whatever will be the pumping length it should work for r1, r2, r3, and r4.

and if I choose pumping length as 2(as you said) it does not satisfy r4. 

here's how I'm getting MPL as 3.

r1 = 0*1 = {1,01,001,0001,......} MPL= 2 from Fact 2

r2 = 0 = {0} MPL = 2 from Fact 5

r3 = 1* = {∈,1,11,111,1111,......} MPL = 1 from Fact 2

r4 = 10*1 = {11,101,1001,10001,.....} MPL = 3 from Fact 2

so MPL for {r1 U r2 U r3 U R4} = Max{ 2, 2, 1, 3} = 3

where am I wrong ? 

 @Deepakk Poonia

0

how did you determine number of states in minimal DFA will be equal to 7.

I constructed mDFA for the given language. With Practice, you'd be able to construct DFA directly without making it from NFA and sometimes, with more practice, You can draw mDFA directly as well for many languages. 

0

why is MPL=1 in question j?

Language is already $\Sigma^*$. So, ALL possible strings already belong to it. And by definition, Pumping length is $\geq 1.$ 

0

where am I wrong ? 

Here you are wrong :

 let me break it down as : r1,r2,r3,r4

so whatever will be the pumping length it should work for r1, r2, r3, and r4.

The moment you broke down. 

Pumping lemma doesn't say that You break down the language. If it were the case that We could break down the language then I could Prove that NO infinite language (Even Infinite Regular languages) would satisfy Pumping lemma. Here's the idea : Break down the given infinite language as Union of infinite Singleton sets of strings. Now, If You pick any Pumping length $P$ and apply it to each individual set (which consist only one string) then NO constant number will satisfy this language. (Why? Think about it.)

So, Apply Pumping lemma For the language, Not the parts of it.   

0

Please edit the question it is Union, not positive closure.

i verified in the book, it is positive closure only but not union !

 

Let take your doubt as a new question : L = 0*1 ∪   0  ∪   1*  ∪   10*1 

By seeing the 10*1 we think, pumping length is 3, but note that, from 11 ( by removing 0* ) also, that is belongs to the language due to 1* , So, 11 is also in our language, let think minimum pumping lemma length is 2. by iterating (let choose y as left 1), y zero or more times the new string which is generated still in our language !

Now you may thought, that, empty string is also in our language, so minimum pumping lemma length is 1.

then there is string "0" in our language, So you have to choose y="0", by repeating zero or more times,

zero times ==> empty string ===> belongs to the language ===> no problem

one times ==> "0" string ===> belongs to the language ===> no problem

two times ==> "00" ===> not belongs to the language ===> problem ==> so minimum pumping lemma length can't be 1.

0
"By seeing the 10*1 we think, pumping length is 3, but note that, from 11 ( by removing 0* ) also, that is belongs to the language due to 1* , So, 11 is also in our language." This Clarify my doubt, 11 from 10*1 was my counter example to prove that MPL is 3 but turns out 11 can be generated by 1* therefore for MPL is 2.  Thanks guys.
0

@Shaik Masthan

Here pumping length can be anything $\geq 2$

So, can we say minimum pumping length can be 100, if string length $\leq 99$ not present in language

+1

@Deepakk Poonia (Dee)

here in the 'e' part of this question, I have a doubt, here  '1' length  string cannot be generated from the given language, so we can say  we can use 1 or more length string s for the pumping that belongs to L,

see the answer of 4th in this question,

https://gateoverflow.in/27476/what-is-the-minimum-pumping-length-the-following-languages

if it is not the case that how the answer of 'h' is 4.

0
yes, for part e, MPL=1 only !
0

@Shaik Masthan

in terms of FA states can we say that the minimum pumping length is the minimum lenght of the input string for which the states in FA starts repeating ?

0
NO... if it is the case, for question e :

the minimum length of the input string which is repeated is 2 i.e, string "01"
0
okay...understood.
0
10*1 = {11,101,1001,10001,.....} MPL = 3 from Fact 2  so   are you saying that  MPL for this is 2  and not 3 So what about fact  2 kindly clear  it
0

MPL of this will be 10*1 will be 3.

we will take x=1 y=0 and z=1 and as we can see all $xy^qz \in L$ where q >=0.

In the above comments they are talking about different language i.e. L = 0*1 ∪   0  ∪   1*  ∪   10*1

By seeing the 10*1 we think, pumping length is 3, but note that, from 11 ( by removing 0* ) also, that is belongs to the language due to 1*

in the above comments we are not talking about language L = 10*1 we are talking about L = 0*1 ∪   0  ∪   1*  ∪   10*1

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,845 questions
54,784 answers
189,426 comments
80,435 users