Skip to main content
4 of 4
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/

Quantification in pumping lemma for regular languages

The Wikipedia article on the pumping lemma states:

We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align*} &(\forall L \subseteq \Sigma^*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align*} $$ I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?