The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
80 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. Σ∗
asked in Theory of Computation by Junior (727 points)
edited by | 80 views

1 Answer

+2 votes
Best 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.

answered by Boss (22.6k points)
edited ago 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.

 

 

0

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.

Related questions

+1 vote
3 answers
2
asked Jun 26, 2017 in Theory of Computation by aaru14 Junior (819 points) | 228 views
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
47,929 questions
52,326 answers
182,372 comments
67,797 users