patternMinor
Where do the length restrictions of the pumping lemma come from?
Viewed 0 times
restrictionsthecomelengthwherepumpinglemmafrom
Problem
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:
Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:
Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:
My question is this: Can someone give a concise and clear explanation of how regularity (context-freeness) imply the first and second conditions above? The pumping length is determined by (finite) properties (finite number of states or finite properties of production rules, respectively), the third properties guarantee that a state (production rule) can be skipped or repeated arbitrarily many times, but where do the first and second conditions originate? How are they justified?
Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:
- $|y|\geq 1$
- $|xy|\leq p$
- $ \forall i\geq 0: xy^iz\in L$
Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:
- $|vy|\geq 1$
- $|vxy|\leq p$
- $ \forall i\geq 0: uv^ixy^iz\in L$
My question is this: Can someone give a concise and clear explanation of how regularity (context-freeness) imply the first and second conditions above? The pumping length is determined by (finite) properties (finite number of states or finite properties of production rules, respectively), the third properties guarantee that a state (production rule) can be skipped or repeated arbitrarily many times, but where do the first and second conditions originate? How are they justified?
Solution
The first condition, i.e. $|y| \geq 1$, is clearly necessary if you want to say something interesting: for $y = \varepsilon$, $xy^iz \in L$ trivially and always holds.
The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker.
But remember what we want to use the pumping lemmas for: we want to find a (sufficiently long) word such that all valid decompositions into $x,y,z$ fail to pump. Therefore, it is useful to allow as few such decompositions as possible. Lucky as we are, the proof of the pumping lemma readily yields a strong restriction, namely that there has to be a pumpable decomposition with $|xy| \leq p$ with constant $p$.
Now we have to refute only finitely many prefixes $xy$ (with possibly infinitely many different continuations, of course). If you look at example applications, you will see that they make heavy use of this restriction.
The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker.
But remember what we want to use the pumping lemmas for: we want to find a (sufficiently long) word such that all valid decompositions into $x,y,z$ fail to pump. Therefore, it is useful to allow as few such decompositions as possible. Lucky as we are, the proof of the pumping lemma readily yields a strong restriction, namely that there has to be a pumpable decomposition with $|xy| \leq p$ with constant $p$.
Now we have to refute only finitely many prefixes $xy$ (with possibly infinitely many different continuations, of course). If you look at example applications, you will see that they make heavy use of this restriction.
Context
StackExchange Computer Science Q#9323, answer score: 8
Revisions (0)
No revisions yet.