# GATE2019-15

14.1k views

For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ?

1. $3$
2. $5$
3. $9$
4. $24$

edited

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

If we talk about DFA then it repeats some states. If we talk about regular grammar then it repeats atleast one nonterminal in derivation.

Let us suppose $p$ is pumping length then any string $w$ that has length greater than $p$ must  have repetition . (In above DFA, for any string which has length $>p$ it has to go through the loop (repeat).)

$S \rightarrow aX \rightarrow \dots \rightarrow aw' X \rightarrow \dots \rightarrow w$

$S \rightarrow aX \rightarrow \dots \rightarrow aw' X \rightarrow \dots \rightarrow aw'w'X \rightarrow \dots \rightarrow w$ (if repeat $X$ 2 times)

If you notice we can generate infinitely many string by choosing number of repetitions to be 1,2,3 or any value.

Does this make any regular language an infinite language? No, we already know that regular languages are finite too.

What goes wrong here?  Nothing.

For finite languages pumping length is greater than the longest string. And the definition of pumping length says that "Any string that is greater than $p \dots$". And there are no string which is greater than $p$ which makes definition trivially true.

Now coming to the easiest part which is solving the question with clear definition in mind.

(First construct DFA)

Option A says that any string that has length $3$ or greater has to have some repetition.

-Obviously false, $b^{10}$ is a string in language and doesn't repeat any state.

Moreover any string with length greater than $10$ needs to repeat states.

edited
9
Any value less than 24 possible? Actually if A or B or C is the answer then D should also be the answer rt? 😄
2
Yes sir, anything greater than $10$ can be pumping length.

The statement goes like this: "Any string in $L$ which has length greater than 10, has to repeat states in DFA."

One might also argue that string with length 12 eg. - $b^{12}$ does not need to repeat states. But this string is not in $L$ at first place.
13

any string in that language with the length $greater \,\,than$ pumping length has some repetition.

anything greater than 10 can be pumping length.

@Sachin Mittal 1, Which formal definition(complete definition) of Pumping lemma(PL) you have used here? Kindly elaborate.

Because the most widely used definition of PL requires that all the strings $w \geq P$ can be pumped. But you have used all the strings $w > P$ can be pumped.  This does make a difference in answering "Minimum Pumping length" for a Regular language.

According to the definition of PL used by most authors like Ullman and wikipedia, the minimum Pumping length for this language will be 12. So, any integer $\geq 12$ is a Pumping length for this language.

2
in case of a, we are getting repeatition after length 2. so why not all options are true?
2

because we have to check for both a as well as strings of b.

0

For Σ={a,b}, let us consider the regular language L={xx=a2+3k }

strings will be

L=a2,a5,a8,a11,a14,a17,a20,a23,a26,a29,a32

now in above a5 5 will be pumping length by breaking a5 into xy^iz a^2(a^3)^1 can we say thtat pumping length = 5 and not 2 or 3 0r 4

0

@Sandeep Verma , The example that you have taken, Minimum pumping length = 3 , (we know that string lengths of 3 can't be generated by the language but that is not our fault and we will not be violating the definition of pumping lemma that says that for any w ∈ L and |w|≥ pumping length).
But if we say pumping length, that can be 3,4 or 5 (definitely not 2).

0
Can you please construct minimum dfa.
0
Why we have not considered (a^2+3k)?

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 but not sufficient condition

i.e. All Regular languages must satisfy this condition and some Non-regular languages also satisfy this condition.

So, Regular Language → Satisfies Pumping Lemma

∴ Contrapositive statement is Doesn't Satisfy Pumping Lemma → Not Regular Languages

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 the language in the Question, this language consists of the following strings.

$L = \{ a^2, a^5,a^8,a^{11},a^{14},........., b^{10},b^{22},b^{34},b^{46}.......... \}$

Let me assume that Pumping length is $P = 10$ (Note that if Minimum pumping length for a language is $x$ then any number $\geq x$ is also a Pumping length for the language )

Since, I have assumed that Pumping length is $P = 10$, so, For all strings whose length is $\geq 10$ should be Pumped i.e. If $w$ is a string of length $\geq 10$ then within the first $P \,\,i.e. 10$ symbols of the string $w$, we should be able to find some non-empty substring $y$, such that we can repeat $y$ Zero or More times and the resulted string still belongs to language $L.$

So, since $w = b^{10}$ has length $\geq 10$ so, $b^{10}$ must be pumped. But in $b^{10}$ , If you take any non-empty substring and you remove that substring (Note that repeating substring $y$ Zero times in $w$ is equivalent to saying that remove $y$ from the string $w$) then resulted string does not belong to the given language. So, Pumping length cannot be 10. And Since we know that if Minimum pumping length for a language is $x$ then any number $\geq x$ is also a Pumping length for the language. So, Since 10 is Not a pumping length for $L$, so, any number $\leq 10$ cannot be a Pumping length for $L.$

So, Option 1,2,3 can be eliminated.

Moreover, The minimum pumping length for this language is $12.$ So, any number $\geq 12$ is a Pumping length for the given language.

Minimum Pumping length for the given language is P =  12 :

Take any string $w$ of length $\geq 12.$

Say, you take $a^{14}$ then the non-empty substring $y$ within the first $P\,\,i.e.12$ symbols can be taken as first three $a's$ i.e. $aaa.$ When you repeat $aaa$ Zero or more times, the resulted string still belongs to the language.

Similarly, for any $a^{2+3k}, k \geq 4$, $y$ can be chosen as the first three $a's$ i.e. $aaa.$ When you repeat $aaa$ Zero or more times, the resulted string still belongs to the language.

Say, you take $b^{22},$  then the non-empty substring $y$ within the first $P\,\,i.e.12$ symbols can be taken as first twelve $b's$ i.e. $b^{12}.$ When you repeat $b^{12}$ Zero or more times, the resulted string still belongs to the language.

Similarly, for any $b^{10+12k}, k \geq 1$, $y$ can be chosen as the first twelve $b's$ i.e. $b^{12}.$ When you repeat $b^{12}$ Zero or more times, the resulted string still belongs to the language.

So, Minimum Pumping length for this given language $L$ is 12. And So, any number $\geq 12$ is a Pumping length for L.

Extra Notes :

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.

More examples to practice Minimum Pumping length : https://gateoverflow.in/303738/michael-sipser-exercise?show=303856#a303856

edited
6

Thank you so very much for the answer! You’re a blessing in disguise. 👏🏼

1

@Deepakk Poonia (Dee)

right?

0

don't forget 001 subset to 0*1*
0

@Shaik Masthan

1. L=001 U 0*1*

I mean this one

yes 001 is substring of $0^{*}1^{*}$

but then $a^{2}$ and $b^{10}$ is not subset of each other

then why $b^{10}$ can be pumping length but $a^{2}$ cannot be pumping length?

0
if you consider only a part, then minimum pumping length is 3 but neither 2 nor 5.

but 3 can not satisfied b part... So for saying minimum pumping length, it should satisfy both parts ==> 12
0

@Shaik Masthan

For  a  pumping length $\geq 3$

So, can we not say min pumping length can be anything $\geq 3$

Same thing is there

L=001 U 0*1*

So, here pumping length $1$ or $4$?

0
what is the problem, if i say it is 1 but not 4 for that problem ?
1
then 001 maynot satisfied in that pumping length
1
Minimum pumping length = 1, and take the string (w) = 001 ==> w ∊ L and  |w| ≥ P, then there should be

Let take x =EMPTY STRING and y=0 and z=01 ===> here |x| = 0, |y|=1 and |xy| ≤ 1

then y=0 times ==> x.z ===> ∈ . 01 = 01 present in our language.

then y=1 times ==> x.y.z ===> 001 present in our language.

then y=2 times ==> x.y.y.z ===> 0001 present in our language.

..... for any i, xy$^i$z in our language, if w=xyz and |w| ≥ pumping length
0
y cannot be 0

right?

$\left | y \right |\geq 1$

and $\left | xy \right |\leq$ Pumping length

What is Pumping length? total length

right?

Then what will be your answer? $1$ or $4$
0
mam, is it ok now ?
1

@Shaik Masthan

yes right.

Pumping length = size of loop

Now, tell me

why pumping length cannot be $\geq 3$

because atleast a could be pumped when loop length 3

@Deepakk Poonia (Dee) ,@Sachin+Mittal1

0

1.

Regular expression(RE) for Language $L$ in $Q2$ is : $001 \cup 0^*1^*$ Which is nothing but $0^*1^*$

For the language $L$ described by this RE, The minimum Pumping length will be $1$ because For All strings of length $\geq 1$, You can pump all such strings by taking first symbol of the string as $y .$ (Refer the definition of Pumping lemma condition in my answer above)  Since MPL is $1$, So any integer number $\geq 1$ is a Pumping length for this language.

2.

yes 001 is substring of $0^∗1^∗$

but then $a^2$ and $b^{10}$ is not subset of each other

then why $b^{10}$ can be pumping length but $a^2$ cannot be pumping length?

001 is Not a Substring of $0^*1^*.$ 001 is generated by the RE $0^*1^*$

$a^2$ and $b^{10}$ are Strings, Not sets. So, being a Subset of each other or not is invalid/off-topic.

$b^{10}$ is a String, It is Not a Pumping length. Pumping length is always a Positive integer, Not a string.

The MPL for the given language is $12,$ Not 10.

3.

For  a  pumping length ≥3

So, can we not say min pumping length can be anything ≥3

L=001 U 0*1*

So, here pumping length 1 or 4?

Minimum Pumping length for any language $L$ is the Least positive integer for which $L$ satisfies the Pumping lemma condition. So, It is a Unique Number.

Let's say, For some language $L,$ $3$ is a Pumping length then You can say that any number $\geq 3$ is also a Pumping length for $L.$

Now, coming to $L=001 \,\,U\,\, 0^*1^* ,$ , For this language we have shown that $1$ is a Pumping length (1 is the MPL for this language) so any number $\geq 1$ is also a Pumping length for this language.

So, $1,4$ both are Pumping lengths for this language.

4.

y cannot be 0

right?

|y|≥1

Length of $y$ cannot be $0.$ $y$ could be $0$ because $|0| = 1$.. $y$ and $|y|$ are Two different things.

What is Pumping length? total length

right?

Pumping length is Some Positive Number associated with Regular languages. (in Propositional logic, this statement would be wrong)

With every Regular language $L$, there is some positive number associated with $L$ such that The Condition of Pumping lemma (stated in the answer above) is satisfied by $L.$

5.

why pumping length cannot be ≥3

because atleast a could be pumped when loop length 3

Read the Pumping lemma condition definition carefully. It says that if $P$ is Pumping length for $L$ then For ALL Strings $w \in L,$ such that $|w| \geq P$, Pumping lemma conditions must satisfy.

0

@Deepakk Poonia (Dee)

are both statement not  contradictory?

if $L=001\cup 0^{*}1^{*}$ has pumping length $1$

and $L=a^{3k}\cup b^{12k}$ has pumping length minimum $12$ , //this contradicts previous one

there is "or" between these two strings, So, if any one satisfied, that should be minimum pumping length

isnot it?

0
can't we write like  $L = 001 \cup 0^*1^* = 0^*1^*$ and then when we calculate pumping length it will become $1$.

but in gate 2019 question we can't apply this concept.
0

Can you please explain "Minimum Pumping length for the given language is P =  12 :" , how it is happening ???

0

@Deepakk Poonia (Dee) Why cant minimum pumping length be 11 for this question. Because any string of length >= 11 can be pumped to get a string that is present in the language.

0

Why cant minimum pumping length be 11 for this question. Because any string of length >= 11 can be pumped to get a string that is present in the language.

If you take pumping length to be $11$ then you can't pump $b^{22}.$ To pump $b^{22},$ you need pumping length at least $12.$

can't we write like  L=001∪0∗1∗=0∗1∗and then when we calculate pumping length it will become 11.

but in gate 2019 question we can't apply this concept.

Of course, we will write $001 \cup 0^*1^* = 0^*1^*.$ Both are one and the same. But I don't see how this is relevant here.

Can you please explain "Minimum Pumping length for the given language is P =  12 :" , how it is happening ???

If you take any number $<12$ as pumping length then you can't pump $b^{22},$ hence you need to take pumping length as at least $12$ and then you can work it out that with pumping length $12,$ you can pump all the strings in the language and the resulting string will be in the language.

0

@Deepakk Poonia (Dee) Now I get it , I ignored |xy|<=m condition, yes , minimum pumping length would be 12. Tysm for explanation.

0

@Deepakk Poonia (Dee)

Sir MPL>=12 ohk? but sir any string greater than 12 should be generated so here length 13 is not present in language itself so it means only those string which is present in language and length greater than 12 will be generated??

2nd doubt when we say MPL is this then we say only mod value right? because in 1st part "a" is repeating and 2nd part 'b' is repeating so we can not say that this is y and this is repeating?? and if we can not say this is y then how can we repeat y??

3rd doubt so we find MPL of both part and take Max value of them for MPL of L??

Would you please tell what is Y here (not MPL)??

0

One more thing sir here MPL is

(1 , 2 , 1 , 2) for all 4 part so we took max of them hence overall MPL=2  right?? 0
Even I used to refer this book

Suggested by Tewari sir from IIT Kanpur
0
Why does an answer having 50 likes is treated as the best answer rather than an answer having 80+ likes?
0
Nepotism here also bro

A language is regular iff:-

• The language is finite; or
• The language is infinite but has some "pattern" in it, that can be replicated by some FA.

This "pattern" means some sort of repetition. Because of such repetitive patterns, we can introduce loops in the FA and make the FA accept the infinite string(s) of the language, making it a regular language.

For an infinite regular language, the (not necessarily minimum) length of the string after which it is certain to display repetitive patterns, is called pumping length. The idea is that such patterns can be "pumped" over and over via loops.

By this information, we know that if x is pumping length, anything greater than x is also pumping length. Because if a language shows repetitive behaviour in length 50, it'll definitely show the same if extra length is added to it.

So, even if Options A, B, C were true; by definition D would also be true. Safest bet is the longest pumping length.

Coming to the actual solution;

$L=\left \{ a^{2}, a^{5}, a^{8}, a^{11},..., b^{10}, b^{22}, b^{34}, b^{46}... \right \}$

Length 3 can't be pumping length because $a^{5}$ will have no repetitions in the DFA

Option A eliminated

Length 5 can't be pumping length because $b^{10}$ will have no repetitions in the DFA

Option B eliminated

Length 9 can't be pumping length because $b^{10}$ will have no repetitions in the DFA

Option C eliminated

The minimum pumping length is 11. NOT 10. Because repetitive string length $\geq$ pumping length for pumping length to be valid.

At length = 10, the language does NOT pump through the FA. But anything with length > 10 will.

Since 24 > 11; hence it also qualifies to be the pumping length. Option D.

1

$MPL$ is not 11. It's $12$. I am not going into a lot of details but I suggest you to go through all the questions in pumping length tag of GO.

$x(y)^iz=\epsilon (b^{12})^ib^{10}|i>=0:$ $\checkmark$

MPL will always be strictly greater than the minimal string in the language.

$x(y)^iz=\epsilon (b^{11})^ib^{11}|i>=0:$ $X$

0

@Kushagra गुप्ता Why can't minimum pumping length be 11, because according to the definition pumping lemma should hold for any string of length >= pumping length "that is present in language", and in this case it is holding up for any string of length >=11 (although language is not generating any string of length 11, but that in any way does not restrict us to take min. pumping length as 11 and also doesn't violate the definition).

0

@Kushagra गुप्ता I got it, never mind!!

0
Can you elaborate why the minimum pumping length would be 12? Because in the accepted answer it is given as 11?
1 vote

Pumping Lemma for Regular Languages :

For a language L , there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and

(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uv^iw ∈ L

We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b10+12k.
The minimum string in L = "bbbbbbbbbb" but this string b10 cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10 .

Pumping Lemma for Regular Languages:
For any language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uviw ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b10+12k.
The minimum string in L = "bbbbbbbbbb" but this string b10 cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10 .
0
Kindly add one more line "this string b^10 cannot be broken down in uvw such that U V^i w belongs to L"
Pumping length is the minimum length, after which every string can be can be considered a combination (xyz), such that x,y and z are any strings belonging to our language.

For example: For above language consider string: a¹¹

a¹¹ can be written as : a⁵a²a²a²

So here x: a⁵ y: a² z: a²

So we can write above string as : xyyz

Note: we can not convert any of the possible combinations of a^n, where n<11 into above mentioned combination.

Basically, pumping length is the length after which we can accept the strings simply by repeating on the states.

So for length of 11 we require a 12 state DFA.

This will be valid for both a and b.

(You can construct and check it)

So basically here my pumping length would be 11 or any value greater than 11.

## Related questions

1
6.4k views
If $L$ is a regular language over $\Sigma = \{a,b\}$, which one of the following languages is NOT regular? $L.L^R = \{xy \mid x \in L , y^R \in L\}$ $\{ww^R \mid w \in L \}$ $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^*$such that$\ xy \in L\}$ $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^*$such that$\ xy \in L\}$
Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free? $\{ww^R \mid w \in \{a, b\}^*\}$ $\{wa^nb^nw^R \mid w \in \{a,b\}^*, n \geq 0\}$ $\{wa^nw^Rb^n \mid w \in \{a,b\}^* , n \geq 0\}$ $\{ a^nb^i \mid i \in \{n, 3n, 5n\}, n \geq 0\}$
Consider the following sets: S1: Set of all recursively enumerable languages over the alphabet $\{0, 1\}$ S2: Set of all syntactically valid C programs S3: Set of all languages over the alphabet $\{0,1\}$ S4: Set of all non-regular languages over the alphabet $\{ 0,1 \}$ Which of the above sets are uncountable? S1 and S2 S3 and S4 S2 and S3 S1 and S4
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______