retagged by
33,876 views
49 votes
49 votes

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$
retagged by

6 Answers

Best answer
158 votes
158 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 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 \in L$ 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 \in L$ 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 : 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.

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


$\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
67 votes
67 votes

Answer: D

Pumping length $P$ for a regular language $L$ makes sure that any string in that language with the length greater than or equal to pumping length has some repetition zero or more times.

This means If you take $w \in L $ such that length of $w$  is greater or equal to $P$ then some part of $w$ can be pumped zero or more times such that resulting string is still in language.

For example, lets take regular language $L = \{ 0^m 1^n | m\geq 0, n\geq 0 \}$. Here suppose somehow I know that pumping length is 1. Now you choose any string having length $\geq 1$ then I will show you which substring you can pump (zero or more times). Note that you are free to remove subtsring (pumping zero times) or pump anytime.

  1. Suppose you choose $00011$ (its length is 5 which is greater than equal to 1)
  2. I say ok, take first 0 and pump it zero or more times.
  3. You: Hmm, pumping first zero 0 times i.e. removing first 0 from $00011$ or pumping one or more times will give string which is still in language.

Which means for any regular language you have pumping length. (Regular language $\rightarrow$ satisfy pumping lemma)

But wait, Above pumping length is 1, can I say pumping length is also 2 ? (Yes, you can take any string which is greater or equal to 2 and pump some substring ot it). 

Lets talk about minimum pumping length (MPL) only. Beacuse of we know MPL then we know all pumping lengths. if MPL = P then P+k is also pumping length for any non-negative k.

We can also see pumping lemma using DFA and even regular grammar.

 

 

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 minimum pumping length then any string $w$ that has length greater than equal to  $p$ must  have repetition(zero or more times) .

(In above DFA, for any string which has length $\geq p$ it has to go through the loop (zero or more times).)

$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 equal to MPL $p \dots$". And there are no string which is greater than equal to MPL $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 equal to $12$ needs to repeat states.

D is the correct answer.

 

This lemma can also be used to test regularity of a language.

edited by
5 votes
5 votes

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 votes
1 votes

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 .

Answer:

Related questions

21 votes
21 votes
7 answers
2
Arjun asked Feb 7, 2019
9,028 views
The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs.break downbreakbreaks downbreaks
11 votes
11 votes
6 answers
3
Arjun asked Feb 7, 2019
5,671 views
The search engine’s business model ____ around the fulcrum of trust.revolvesplayssinksbursts
8 votes
8 votes
4 answers
4