Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and
My question is, what exactly is the "Pumping Length" $n$ here? While proving if a language is regular or non-regular, do I have to assume the value of $n$, or do I have to calculate it? If Yes, how to calculate?
The pumping length $n$ must be assumed to be arbitrary - you can't fix it to be a particular value. The pumping lemma is used to prove that a given language is nonregular, and it is a proof by contradiction.
The idea behind proofs that use the pumping lemma is as follows. To prove a given language $L$ is nonregular, by way of contradiction, assume that $L$ is regular. Then there must be a machine on $n$ states accepting $L$, for some positive integer $n$. You can then show (this is essentially what the proof of the pumping lemma does) that such a machine must also accept other strings, i.e. $L$ must also contain these other strings (these other strings are the pumped strings, which have the form $xy^iz$). However, it can be shown that some of these pumped strings do not belong to the given language, and so we have a contradiction. This contradiction implies that the assumption you started with (that there is a machine with $n$ states accepting $L$) is false, i.e. there is no machine on $n$ states accepting $L$. Since $n$ was chosen to be arbitrary, you've shown that there does not exist a machine on any number of states accepting $L$, i.e. there does not exist a machine accepting $L$.
The "Pumping Length" "n" exists because you can write a finite automata that classifies all strings up to a fixed, finite length in any way it wants to.
Your finite automata can have (in effect) a lookup table, and decide where each string goes (accepted or not accepted).
But, you cannot make an infinite lookup table. The program/machine/expression for recognizing regular languages only has so much state. How much state isn't known -- because you can make really, really large finite automata -- so we cannot fix an "n" that works for all machines.
Instead, it is saying that for every fixed finite automata, there is a length of string long enough that the finite automata cannot maintain an arbitrary lookup table. As we don't know how big the automata is, we don't know how long this string has to be.
You could write an algorithm that takes a given regular language (assuming it is described reasonably) and produces the point where it cannot hope to maintain a lookup table. As an example: if your recognizing machine was a finite automata description, once your string is longer than the number of states in the finite automata, it must have formed a loop (visited a state twice).
If we break the recognized string into 3 parts (the part before we start the loop, the part that walks the loop, and the part afterwards), we can repeat the loop part of the string any number of times.
But in this proof, and in general, we don't have the finite automata.
But we do know if the language is regular, then such an "n" exists.
So when proving a language non-regular, if you can prove that for every single n, the pumping lemma doesn't hold for any string of your choice, you win.
On the other hand, if you prove the pumping lemma holds for given string in the language, that does not prove the language is regular.
This kind of mental gymnastics is tricky, honestly.
You can rephrase this as a challenge-response. To prove a language is non-regular, you need to make a proof machine.
This proof machine must accept a value "n". It must then produce a string x with |x| > n.
Then it must accept any subdivision of x into uvw with |v| > 0 and |uw| <= n. From that, it has to prove that uv^iw is not in the language.
The choice of "n" and the "uvw" are hostile, not something you get to pick. Your "proof machine" must work regardless of what values it is challenged with.
If you can do this, you have proven the language is non-regular.
When using the pumping lemma, you do assume such $p$ exists, assuming that the language is regular. This $p$, no matter what it is, should exists since it is the number of states for the DFA of the language. You do not however need to know its exact value, it must exists if the language is regular.
You can read it in the proof of the pumping lemma .
A regular language has a finite state machine, and therefore it has a finite state machine with a minimum number of states n. If we examine the first n letters of an input string, there are n+1 states that we encountered after 0, 1, 2, …, n letters. Since there are no n+1 states, there must be a state S that we encountered after x letters and after x < y <= n letters, so in the state S the next y-x letters brought us back to the same state S. Whether we parsed those letters 0, 1, 2, or any number of times, we go back to the same state S.
And if you look carefully, that’s exactly what the pumping Lemma says. The pumping length is any number the number of states in the smallest finite state machine for the language. (Except that we don’t greater than that number of states, and we usually use the pumping Lemma to show that the language is irregular and therefore the number of states and the pumping length don’t exist).
