When applying pumping lemma for regular languages to prove that a given language is non regular, do we show that pumping fails for all $i$ or one $i$?

Question

Pumping Lemma for Regular Languages

Pumping Lemma for Regular Languages: If $A$ is a regular language, then there is a number $p$ ( the pumping length ) where if $s$ is any string in $A$ of length atleast $p$, then $s$ may be divided into three pieces, $s=xy$, satisfying the following conditions:

1. $for \ each \ i>=xy^iz∈A$,
2. $|y|>0$, and
3. $|xy|<=p$

When using pumping lemma to prove that a given language is "non regular, we do the following steps:

1. Assume $L$ is regular, hence $L$ exhibits pumping lemma for regular langauges
2. Since $L$ is regular, it will have $p$ and if we choose a string that is atleast as long as $p$
3. Then that string will have decompositions satisfying all the three conditions of the lemma
4. This is where we obtain a contradiction by showing that the string will fail to satisfy condition 1 of the lemma and hence our assumption is false and the language is not regular

My question is: Do we need to show that the string fails to satisfy condition 1 for one $i$ or all $i>=0$. I do understand that we need to show that string fails to satisfy for one $i$ but should the proof be able to extrapolate for any value of $i>=0$?

My understanding is that: In order to have a strong valid contradiction, we need to show that our string choice and pumping of the string fails for all values of $i$ according to condition 1

But when we say "for all values of $i>=0$", we know that for $i=1$, the pumped string does exist in the language( because we chose that string ), and sometimes it also exists in the langauge for $i=0$, so are these sort of exceptions?

Answer 1

Assuming the rest of the proof is formulated correctly, showing that every $xyz$ division fails to be pumped for at least a single value of $i$ is sufficient. To see this, let's inspect the formal definition of the pumping lemma, which states the following: (note the highlighted quantifiers)

For every regular language $L$, there exists an integer $p$ such that for every string $s \in L$ with $|s| \geq p$ there exists a way to partition $s$ into $xyz$ such that

• $|xy| \leq p$
• $|y| > 0$
• $xy^iz \in L$ for every $i \geq 0$

We use the lemma in proofs by contradiction: hence, for all points where the lemma states that something must hold "for every" value of something, a single counter-example will be enough. Conversely, when the lemma states that something "exists", you must establish that no satisfactory value exists.

Usually, the way this is done is assuming a valid value of $p$ exists, then selecting a suitable string as we are allowed to, then examining all possible ways to partition the string and establish they fail at least one of the three conditions – usually ruling out the two first conditions, them being more trivial, and then showing each of the remaining possibilities violates the third condition for at least one value of $i$.

Intuition

Remember the pumping lemma is based on the behavior of the automaton recognizing the regular languages, a DFA. The intuition of the lemma is that for an automaton and its language $L$, a sufficiently long string must visit one of the states twice or more when being recognized. This means there is a loop in the string's "execution trace" on the DFA, and therefore a sequence of symbols $y$ that can be repeated to re-trace the loop arbitrarily many times, end in the same state, and continue from there to the accepting state.

Imagine the state that's the start and end of the loop. Since no many how times we pass through the loop, we end up in this state, it follows that we could also execute the loop zero times and cut out the portion of the string that caused our string to loop even once, and not change the acceptance of our string. For any string of a regular language, we could indeed do this – but if this results in a string that no longer belongs in our language, it proves that such a loop did not exist in the first place, confirming the language's non-regularity.