patternMinor
What exactly is pumping length in pumping lemma?
Viewed 0 times
whatlengthpumpinglemmaexactly
Problem
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?
- $|uv| \leq n$
- $|v| > 0$
- $uv^iw ∈ \mathbb{L} \space\forall i\geq0$
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?
Solution
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 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$.
Context
StackExchange Computer Science Q#151311, answer score: 3
Revisions (0)
No revisions yet.